n******n
发帖数: 49 | 1 Given a list of words with a same size and a big string that
contains one of the permutation of all the words combined(say p),
find the start index of the string p in the big string.
现在能想到的解法就是：
- find the positions of all the words in the big string
- if you mod with the size of word(same for all words)
should give the same value for all the word positions in the big string and
the lowest position is the startindex.
不知道大家有什么更好的办法没有？这题要用trie吗？ |
g**********y
发帖数: 14569 | 2 Did I misunderstand anything? This sounds like find substring(k*L, k*L+L) ==
p?
L is length of p.
and
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 n******n 的大作中提到】
: Given a list of words with a same size and a big string that
: contains one of the permutation of all the words combined(say p),
: find the start index of the string p in the big string.
: 现在能想到的解法就是：
: - find the positions of all the words in the big string
: - if you mod with the size of word(same for all words)
: should give the same value for all the word positions in the big string and
: the lowest position is the startindex.
: 不知道大家有什么更好的办法没有？这题要用trie吗？
|
n******n
发帖数: 49 | 3 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
a****u
发帖数: 1537 | 4 build the prefix tree of the word list. Scan the long string to check if it'
s match. |
d*******l
发帖数: 338 | 5 假设有m个单词每个长为L，big string的长度为n。
可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
就行。总的复杂度是nL。
and
【在 n******n 的大作中提到】
: Given a list of words with a same size and a big string that
: contains one of the permutation of all the words combined(say p),
: find the start index of the string p in the big string.
: 现在能想到的解法就是：
: - find the positions of all the words in the big string
: - if you mod with the size of word(same for all words)
: should give the same value for all the word positions in the big string and
: the lowest position is the startindex.
: 不知道大家有什么更好的办法没有？这题要用trie吗？
|
b*****i
发帖数: 262 | 6 你所说的解法中，为什么要用trie？用hashtable应该更好啊。时间复杂度是n。
i+
count
【在 d*******l 的大作中提到】
: 假设有m个单词每个长为L，big string的长度为n。
: 可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
: 2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
: 连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
: 就行。总的复杂度是nL。
:
: and
|
d*******l
发帖数: 338 | 7 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。
【在 b*****i 的大作中提到】
: 你所说的解法中，为什么要用trie？用hashtable应该更好啊。时间复杂度是n。
:
: i+
: count
|
n******n
发帖数: 49 | 8 Given a list of words with a same size and a big string that
contains one of the permutation of all the words combined(say p),
find the start index of the string p in the big string.
现在能想到的解法就是：
- find the positions of all the words in the big string
- if you mod with the size of word(same for all words)
should give the same value for all the word positions in the big string and
the lowest position is the startindex.
不知道大家有什么更好的办法没有？这题要用trie吗？ |
g**********y
发帖数: 14569 | 9 Did I misunderstand anything? This sounds like find substring(k*L, k*L+L) ==
p?
L is length of p.
and
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 n******n 的大作中提到】
: Given a list of words with a same size and a big string that
: contains one of the permutation of all the words combined(say p),
: find the start index of the string p in the big string.
: 现在能想到的解法就是：
: - find the positions of all the words in the big string
: - if you mod with the size of word(same for all words)
: should give the same value for all the word positions in the big string and
: the lowest position is the startindex.
: 不知道大家有什么更好的办法没有？这题要用trie吗？
|
n******n
发帖数: 49 | 10 我对题意的理解是：
比如
the list of words with the same size: abc, def, ghi
the big string: xxxdefghiabcxxxxxx
应该返回3，因为defghiabc是一个(abc, def, ghi)的permutation, 它在big string中
起始index是3. |
|
|
a****u
发帖数: 1537 | 11 build the prefix tree of the word list. Scan the long string to check if it'
s match. |
d*******l
发帖数: 338 | 12 假设有m个单词每个长为L，big string的长度为n。
可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
就行。总的复杂度是nL。
and
【在 n******n 的大作中提到】
: Given a list of words with a same size and a big string that
: contains one of the permutation of all the words combined(say p),
: find the start index of the string p in the big string.
: 现在能想到的解法就是：
: - find the positions of all the words in the big string
: - if you mod with the size of word(same for all words)
: should give the same value for all the word positions in the big string and
: the lowest position is the startindex.
: 不知道大家有什么更好的办法没有？这题要用trie吗？
|
b*****i
发帖数: 262 | 13 你所说的解法中，为什么要用trie？用hashtable应该更好啊。时间复杂度是n。
i+
count
【在 d*******l 的大作中提到】
: 假设有m个单词每个长为L，big string的长度为n。
: 可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
: 2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
: 连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
: 就行。总的复杂度是nL。
:
: and
|
d*******l
发帖数: 338 | 14 如果是普通的hashtable，计算一个word的hash值至少是O(L)的，加上一些别的开销，
可能还不如trie最多访问L个节点效率高。如果用类似rabin-karp里那种hash，就是通
过前面的单词的hash值O(1)时间计算出后面的单词的hash值，就需要解决冲突来保证正
确性。我觉得都是可以的，hashtable也不是一定就会更好。
【在 b*****i 的大作中提到】
: 你所说的解法中，为什么要用trie？用hashtable应该更好啊。时间复杂度是n。
:
: i+
: count
|
H***e
发帖数: 476 | 15 没看懂
"并且对于每个
连续的m个这样的子串判断是否m个单词都出现过"
为什么复杂度里面这里没有 m?
i+
count
【在 d*******l 的大作中提到】
: 假设有m个单词每个长为L，big string的长度为n。
: 可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
: 2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
: 连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
: 就行。总的复杂度是nL。
:
: and
|
k***t
发帖数: 276 | 16 如果以m为单位从后往前比，还可以每次向前跳up to mL个字符。
i+
count
【在 d*******l 的大作中提到】
: 假设有m个单词每个长为L，big string的长度为n。
: 可以先建起所有单词的trie tree。然后对于i in [0,L)，对p[i+0..i+L-1],p[i+L..i+
: 2*L-1],p[i+2*L..i+3*L-1]...这些子串在trie中搜索是否是某个单词，并且对于每个
: 连续的m个这样的子串判断是否m个单词都出现过，这个用一个长位L的数组记录下count
: 就行。总的复杂度是nL。
:
: and
|
