20180322 今日算法

[gbin]

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

给定一个字符串 s，和一个由多个长度相等的单词组成的列表，查找 s 中的子字符串的所有起始索引，该子串是由单词列表中每个单词拼接而成的。
例如，给定:
s: "barfoothefoobarman"
words: ["foo", "bar"]
应该返回: [ 0，9 ]。
(顺序不考虑)。

[lhx2008]

我猜是滑动窗口 + map 的那种问题，但是没有想到好的办法，主要是中间会夹插其他单词也算。。而且还可能有两个这样的子串，一个是不完整的，一个是完整的，扫的时候怎么重置也很难判断。

[lhx2008]

再想了下，不存在说上面说的两个子串问题，那就比较好办了，a,b 双指针，间隔单词个长度，右移，直到匹配到第一个单词，a 就固定。b 继续走，检查 b 前单词个长度是不是单词列表里面的，直到单词列表里面全部标记完，暂存 b，然后 b 继续走，看看还有没单词是在单词列表里面的，有就更新暂存的 b
最后到尾巴返回 a 暂存 b 就行

[zqqian]

ac 自动机跑一遍就可以了吧。。

[holyghost]

rolling hash ？

[victor97]

hash + dp

[FenGuWu]

dfa 算法