字符串算法:KMP算法

字符串:由若干个字符组成的有序序列

字符串：末尾有一个隐含的结束符’\0' 字符数组：末尾没有隐含结束符

字符串匹配问题:给出一个主串p 和一个模式串s，问s有没有在p中出现过，出现过几次，每次出现位置在哪里

p:dfghahjsgfhjas—>m s:hjdj—>n

1.BF算法(暴力匹配) O(n*m) for(int i = 0;i + LS < LP ;++i) { int j(0); int k(i); while(j < LS) { if(p[k] == s[j]) { ++j; ++k; } else { break; } } if(j == LS) { cout « i « endl; } }

2.KMP算法 O(n+m) next[0]=-1 next[1]=0 //以上均为默认 代码思路:模式串自己(错位)匹配自己