j**l
发帖数: 2911 | 1 什么KMP, Rabin-Karp, BM, Suffix Tree, Suffix Array, 能用上的请尽量用
1. Write a function f(a, b) which takes two character string arguments and
returns a string containing only the characters found in both strings in the
order of a. Write a version which is O(n^2) and one which is O(n).
2. Given that one of the strings is very very long , and the other one could
be of various sizes. Windowing will result in O(N+M) solution but could it
be better? May be NlogM or even better?
3. Given that you have one str | h**6
发帖数: 4160 | 2 第一题，遍历b串用256数组记录出现过的字符，出现过设为1，没出现过设为0。
然后遍历a串同时检测数组，为1的加入返回字符串中。
其他的等待高手解答。 | l*****a
发帖数: 14598 | 3 1.
for O(n^2) just use LCS(the longest common subsequence)
for O(n),create a hashtable for b and scan a to see whether each of
the characters are in the hashtable or not
2.
i can't understand what u want
3.
Rabin-karp
4.
a hash table stores the ocurrance of each word,a minimum heap of size 10
which contain the ten most frequent words.
pay attention once the memory can't hold all the words,need some ways to
solve.
such as divide them into K parts,each part use the same and find the top
10,then
【在 j**l 的大作中提到】
: 什么KMP, Rabin-Karp, BM, Suffix Tree, Suffix Array, 能用上的请尽量用
: 1. Write a function f(a, b) which takes two character string arguments and
: returns a string containing only the characters found in both strings in the
: order of a. Write a version which is O(n^2) and one which is O(n).
: 2. Given that one of the strings is very very long , and the other one could
: be of various sizes. Windowing will result in O(N+M) solution but could it
: be better? May be NlogM or even better?
: 3. Given that you have one str
| c******f
发帖数: 2144 | |
|
