KMP字符串模式匹配详解(五)

下面是模式值使用第二种表示方法的匹配函数（next[0]=0）

int my_KMP(char *S, char *T, int pos) 
{ 
int i = pos, j = 0;//pos(S 的下标0≤pos<StrLength(S)) 
while ( S[i] != '\0' && T[j] != '\0' ) 
{ 
    if (S[i] == T[j] ) 
     { 
         ++i; 
             ++j; // 继续比较后继字符
     } 
   else             // a b a b c a a b c 
                    // 0 0 0 1 2 0 1 1 2 
   {              //-1 0 -1 0 2 -1 1 0 2 
      i++; 
     j = next[j];     /*当出现S[i] !=T[j]时，
              下一次的比较应该在S[i]和T[next[j]] 之间进行。要求next[0]=0。
在这两个简单示范函数间使用全局数组next[]传值。*/ 
   } 
}//while 
if ( T[j] == '\0' ) 
    return (i-j); // 匹配成功
else 
     return -1; 
} // my_KMP 

 

六．后话--KMP的历史

[这段话是抄的]

Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knuth 和Pratt努力地重建了 Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是“灵光一现”中被发现的，而理论化的计算机科学确实在一些时候会应用到实际的应用中。