kmp算法不懂啊！！！！！！！！1

omxian

有没人指点下，给个完整的程序参考下，谢谢

仰望天上的光

1. //模式匹配,kmp算法,复杂度O(m+n)
   
2. //返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度
   
3. //可更改元素类型,更换匹配函数
   
4. #define MAXN 10000
   
5. #define _match(a,b) ((a)==(b))
   
6. typedef char elem_t;
   
7. 
   
8. int pat_match(int ls,elem_t* str,int lp,elem_t* pat){
   
9.         int fail[MAXN]={-1},i=0,j;
   
10.         for (j=1;j<lp;j++){
    
11.                 for (i=fail[j-1];i>=0&&!_match(pat[i+1],pat[j]);i=fail[i]);
    
12.                 fail[j]=(_match(pat[i+1],pat[j])?i+1:-1);
    
13.         }
    
14.         for (i=j=0;i<ls&&j<lp;i++)
    
15.                 if (_match(str[i],pat[j]))
    
16.                         j++;
    
17.                 else if (j)
    
18.                         j=fail[j-1]+1,i--;
    
19.         return j==lp?(i-lp):-1;
    
20. }
    

复制代码

仅给出函数，最好去数据结构与算法版叫人解释，这个问题发在这里有点不合适。

omxian

仰望天上的光 发表于 2011-11-5 11:59

                               
登录/注册后可看大图

仅给出函数，最好去数据结构与算法版叫人解释，这个问题发在这里有点不合适。

感谢。。。