这是一个创建于 2956 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 ]。
(顺序不考虑)。
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 ]。
(顺序不考虑)。
 | 1 lhx2008 2018 年 3 月 22 日 via Android 我猜是滑动窗口 + map 的那种问题，但是没有想到好的办法，主要是中间会夹插其他单词也算。。而且还可能有两个这样的子串，一个是不完整的，一个是完整的，扫的时候怎么重置也很难判断。 |
| 2 lhx2008 2018 年 3 月 22 日 via Android  1 再想了下，不存在说上面说的两个子串问题，那就比较好办了，a,b 双指针，间隔单词个长度，右移，直到匹配到第一个单词，a 就固定。b 继续走，检查 b 前单词个长度是不是单词列表里面的，直到单词列表里面全部标记完，暂存 b，然后 b 继续走，看看还有没单词是在单词列表里面的，有就更新暂存的 b 最后到尾巴返回 a 暂存 b 就行 |
 | 3 zqqian 2018 年 3 月 22 日 via Android ac 自动机跑一遍就可以了吧。。 |
 | 4 holyghost 2018 年 3 月 22 日 via iPhone rolling hash ？ |
 | 5 victor97 2018 年 3 月 22 日 via Android hash + dp |
 | 6 FenGuWu 2018 年 3 月 22 日 via Android dfa 算法 |
Select Language