r******n
发帖数: 170 | 1 找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba B:ababa, 那
么返回2.
只收了O(n*m)的暴力算法，请问最优的，谢谢！ |
q***y
发帖数: 24 | 2 kmp改一点
把A做一个自动机，B在A自动机上过一遍
O(n)
【在 r******n 的大作中提到】
: 找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba B:ababa, 那
: 么返回2.
: 只收了O(n*m)的暴力算法，请问最优的，谢谢！
|
w****x
发帖数: 2483 | |
i******e
发帖数: 273 | 4 用DFA的是rabin karp吧？
把KMP改成匹配成功以后如果text string (B) 还没结束，
i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
function对应的位置继续匹配
ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
直到text string 结束，用一个counter记录匹配的次数
【在 q***y 的大作中提到】
: kmp改一点
: 把A做一个自动机，B在A自动机上过一遍
: O(n)
|
q***y
发帖数: 24 | 5 rabin karp是什么？
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
|
x*******6
发帖数: 262 | 6 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
node
的subtree有几个leaf。线性复杂度 |
Z*****Z
发帖数: 723 | 7 写个练手
public static void main(String[] args) {
System.out.println(countOccurrence("gcagagagcagagag", "gcagagag"));
}
public static int countOccurrence(String haystack, String needle){
char[] str = haystack.toCharArray();
char[] pattern = (needle + '\0').toCharArray();
int n = needle.length();
int[] table = buildFailureTable(pattern);
int count = 0;
int i = 0, j = 0;
while(i < str.length){
while(j > 0 && pattern[j] != str[i]){
j = table[j];
}
i ++;
j ++;
if(j == n){
count ++;
j = table[j];
}
}
return count;
}
private static int[] buildFailureTable(char[] pattern) {
int[] arr = new int[pattern.length];
int i = 0;
int j = -1;
arr[0] = -1;
while(i < arr.length - 1){
while(j >= 0 && pattern[i] != pattern[j]){
j = arr[j];
}
i++;
j++;
if(pattern[i] == pattern[j]){
arr[i] = arr[j];
} else {
arr[i] = j;
}
}
return arr;
}
【在 i******e 的大作中提到】
: 用DFA的是rabin karp吧？
: 把KMP改成匹配成功以后如果text string (B) 还没结束，
: i) 如果text string中的字符可以重复使用， 则pattern (A) 退回到当前prefix
: function对应的位置继续匹配
: ii)如果text string中的字符不能重复使用， 则从pattern (A) 当前位置继续匹配
: 直到text string 结束，用一个counter记录匹配的次数
|
i******e
发帖数: 273 | 8 见CLRS 3rd Edition pp.990-995
【在 q***y 的大作中提到】
: rabin karp是什么？
|
h******8
发帖数: 278 | 9 正准备换工作，请教大牛们，我也研究生CS，没学过这末复杂的算法，你们都是自学的
？我看了下CLRS，天书一样,一下泄气了大半。
【在 i******e 的大作中提到】
: 见CLRS 3rd Edition pp.990-995
|
f******h
发帖数: 45 | 10 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。
【在 x*******6 的大作中提到】
: 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
: node
: 的subtree有几个leaf。线性复杂度
|
g**e
发帖数: 6127 | 11 O(n)
http://pdf.aminer.org/000/979/588/space_efficient_linear_time_c
【在 f******h 的大作中提到】
: 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。
|
