请高手详细讲讲KMP算法（谢谢先）
偶看此算法时觉的书上讲的很乱，而且有的地方有些问题，请高手帮忙讲一下。 问题点数：50、回复次数：9Top
1 楼UNIXwlc（Hi，神仙姐姐）回复于 2004-11-04 14:12:35 得分 5
KMP关键是要求出字符串的特征向量，所谓匹配的最长前缀串，得出这个，其他的就好说了。
特别注意算法时间开销是O(n)，理解了其原因，算法的内涵就很清楚了。
详细细节请参考部分书籍，推荐：
《数据结构与算法》 许卓群 张铭等 2004 高教版
《The Art of Computer Programming》 Knuth D E. vol 1-3Top
2 楼aaalife（秋天怎么还不来...）回复于 2004-11-04 14:33:47 得分 15
这是我以前给别人讲的
你先看看
要是还不懂的话 提出来
严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。
80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。
我们继续往下看：
现在讨论一般情况。
假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p（m）’
把课本上的这一段看完后，继续
现在我们假设 主串第i个字符与模式串的第j（j<=m）个字符‘失配’后，主串第i个字符与模式串的第k（k<j）个字符继续比较
此时，s（i）≠p（j）, 有
主串： S（1）…… s（i-j+1）……s(i-1) s(i) ………….
|| (相配) || ≠（失配）
匹配串： P（1） …….p（j-1） p(j)
由此，我们得到关系式
‘p(1) p(2) p(3)…..p（j-1）’ = ’ s（i-j+1）……s(i-1)’
由于s（i）≠p（j），接下来s（i）将与p（k）继续比较，则模式串中的前（k-1）个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j),
‘p(1) p(2) p(3)…..p（k-1）’ = ’ s（i-k+1）s（i-k+2）……s(i-1)’
即：
主串： S（1）……s（i-k +1） s（i-k +2） …… s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串： P（1） p（2） ……. p(k-1) p(k)
现在我们把前面总结的关系综合一下
有：
S（1）…s（i-j +1）…s（i-k +1） s（i-k +2） …… s(i-1) s(i) ……
|| (相配) || || || ≠（失配）
P（1） …….p（j-k+1） p(j-k+2) ….... p（j-1） p(j)
|| (相配) || || ?(有待比较)
P（1） p（2） ……. p(k-1) p(k)
由上，我们得到关系：
‘p(1) p(2) p(3)…..p（k-1）’ = ’ s（j-k+1）s（j-k+2）……s（j-1)’
接下来看“反之，若模式串中存在满足式（4-4）。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。（伪代码）
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。
课本83页不是有个例子吗？就是 图4.6
你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！
Top
3 楼free12345（）回复于 2004-11-04 19:46:37 得分 0
楼上的朋友，能贴一下算法，我手中的书和你的不一样啊
我现在急需NEXT[]的算法啊Top
4 楼aaalife（秋天怎么还不来...）回复于 2004-11-04 22:45:39 得分 0
自己hao
Top
5 楼aaalife（秋天怎么还不来...）回复于 2004-11-05 06:36:00 得分 0
自己找去Top
6 楼avalonBBS（"︶.︶メ)→(￣ε￣メ）回复于 2004-11-05 15:02:55 得分 20
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T[i]!=T[j+1]&& j>=0 )
j=next[j] ; //递推计算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
Top
7 楼avalonBBS（"︶.︶メ)→(￣ε￣メ）回复于 2004-11-05 15:05:29 得分 0
同意 aaalife(（秋天怎么还不来～～）) 的话：）
照着例子试着自己推一下next,然后再找几个题来做做就会熟悉了：）Top
8 楼happycock（SSWW）回复于 2004-11-05 22:56:52 得分 10
书上是误导，不是说从前往后滑动多少字符，其实是从后往前滑动多少字符，虽然结果是从前往后计算的。只要你从后往前匹配就明白了。Top
9 楼UNIXwlc（Hi，神仙姐姐）回复于 2004-12-30 15:08:14 得分 0
我看了严老师DS的Demo，感觉和北大教材上的有些出入！
不过核心思想差不多：匹配时，保证目标串S的游标不向左退，尽量使模式串右移。Top
