数据结构书上不是有吗？

不是很明白~~！为什么要这昂求？？？

[quote]不是很明白~~！为什么要这昂求？？？[/quote]

For Example:

主串： abcdfcdfcdecdeffee
模式串：  cdfcde

1<-- a
  -- c （失败，从下一个开始）
2<-- ab 
  --  c （失败，从下一个开始）
3<-- abc
  --   c （成功，继续下一个字母的匹配）
4<-- abcd
  --   cd （成功，继续下一个字母的匹配）
5<-- abcdf
  --   cdf （（成功，继续下一个字母的匹配）
.......
6<-- abcdfcdf
  --   cdfcde （失败，从中可以发现许多。。。）
到这里时如果用一朴素的方法是这样：
-------------------------------------------
 从主串的第4个位置重新匹配！
 7<-- abcd
   --    c
  显然这样做下去是可以匹配成功，但是耗时为O(n^2)!
-------------------------------------------
=================================================
此时我就HA了！
在没有接处KMP时，我自己就有这种想法，我发现80后就是不一样！
为什么这样的方法就成了KMP的专利了，为什么会这样子呢？
ok That's so sad !
==================================================

另外一种方法：
------------------------------------------------------
很显然,可以直接从主串第6个字母开始匹配！！！
理由是：前面的不可能！！！可以PASS！！！
所以关键是怎样求出：可以PASS多少位！！！

这里引用一下老严的方法：
(我觉得和我自己想的很相似）

============== 求NEXT的算法 ===================
void next ( char *moT,int *next,int len)
{
     int i=1,j=0 ; // 其实是KMP算法的自相拟过程！！！
     next[1] = 0 ;
      
     for ( ; i < len ; )
     {
           if (j == 0 || moT[i] ==  moT[j] )
           {
                 i++ ;
                 j++ ;
                 if ( moT[i]==moT[j] )
                   next[i] = next[j] ;
                 else
                   next[i] = j  ;
           }
            else
             j = next[j] ;
     }    
}

=============KMP 匹配算法 ======================

void kmp ( char *mainT,int lmainT, char *moT, int lmoT,char *next,int start )
{
   int i=start , j = 1 ;
    
    for( ; i <= lmainT && j <= lmoT ; )
    {
        if ( j== 0 || mainT[i] = moT[j] )
        {
              i ++ ;
              j ++ ;
        }
        else
        j = next[j] ;
       
    }
       
     if ( j > lmoT )
      return i - lmoT ;
     else
      return 0 ;
 }
         
=========================end ===================