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