lzh

KMP算法是一种高效的模式匹配算法，复杂度可以达到O(m+n)，而普通模式匹配算法的复杂度为O(m*n)。

普通模式匹配算法

　　从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则从主串本次开始比较的字符的下一个字符开始，与子串的第一个字符进行比较（即主串需要回退到本次比较开始字符的下一字符，模式串回退到首字符，主串与子串都需要回退）。
　　匹配成功的标志：比较到子串的’\0’
　　匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。
　　算法复杂度：O(m*n)

KMP算法

KMP算法的改进思路
　　在普通匹配算法中子串与模式串都需要回溯，但这些回溯不是必要的。因为当某一位发生失配时，可以根据已匹配的结果进行判断。该算法问题可以理解为，当模式串中的第k位与主串的第i位比较时发生不匹配时，需要将模式串向右滑动到哪里继续与主串的第i位进行比较？避免了不必要的主串回溯，减少了模式串回溯的位数，从而使算法复杂度提升到O(m+n)。

KMP算法的实现思路
　　从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则将模式串右移至合适的位置，找出模式串中合适的第k位与主串中发生不等的位进行对齐比较。算法继续。
　　模式串与主串对齐继续比较的第k位必须满足其前k-1位与主串发生失配位置的前k-1位匹配，且该k-1位字串必须是最长的字串（即不存在k’>k，使模式串中的前k’-1位与主串发生失配位置的前k’-1位匹配，这是为了保证不漏过可以匹配的串）。
　　该算法中的主程序同普通的匹配算法类似，区别在于当发生不匹配时，主串指针不需要回退（不动），将模式串右移到合适的位置继续进行比较。当模式串移动到第一位（下标为0）仍然不等时，主串指针右移一位。该算法的关键是模式串next[]的取得。
　　匹配成功的标志：比较到子串的’\0’
　　匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。

next[]数组的获得
　　next[]数组记录了当模式串第j位发生失配时，模式串需要移动到第k位，使第k位与主串发生失配的位对齐继续比较（next[j]=k）。next[]数组使用递推实现，假设next[j]=k已经获得，则从next[j]开始推next[j+1]。具体算法如下。
　　假设next[j]=k（第j位及之前的next[]值已经求得，k<j），当模式串第j位发生失配时，模式串需要移动到第k位，使第k位与主串发生失配的位对齐继续比较。这说明：除了第k位，其前面的k-1位与主串发生失培的前k-1位已经匹配。（因为当第p[k]位失配时，p[1]p[2]…p[k-1]已经等于s[i-k+1]s[i-k+2]…s[i-1]）
　　而同时由于：p[j-k+1]p[j-k+2]…p[j-1]=s[i-k+1]s[i-k+2]…s[i-1]
　　所以：p[1]p[2]…p[k-1]= p[j-k+1]p[j-k+2]…p[j-1]

情况1：
　　若p[k]=p[j]，即p[next[j]]=p[j]，那么：p[1]p[2]…p[k-1]p[k]= p[j-k+1]p[j-k+2]…p[j-1]p[j]，则根据定义：next[j+1]=k+1=next[j]+1

情况2：
　　若p[k]!=p[j]，即p[1]p[2]…p[k-1]p[k]!= p[j-k+1]p[j-k+2]…p[j-1]p[j]，即p[k]与p[j]发生不等。把p[k]为模式串，即模式串第k位发生失配，根据KMP算法的基本思路，当模式串第k位发生失配时，模式串应移动到第next[k]=k’位与主串进行比较。此时：p[1]p[2]…p[k’-1]= p[j-k’+1]p[j-k’+2]…p[j-1]。然后再比较p[k’]与p[j]，若相等，同情况1：next[j+1]=k’+1= next[k]+1；若不相等，返回到情况2的头进行比较。（两种判断均可以归入情况1或者情况2，所以可以进行循环）

情况3：
　　若next[k]=-1，即发生失配元素的前一个元素与第一个元素a[0]仍然不等，该应使该失配元素直接与第一个元素比较，next[j+1]=0。（该情况可与第一种情况合并（因为next[0]=-1））

简单得说：
　　从next[j]=k开始比较，首先将k与自身对齐比较（找可以与j对齐比较的最长子串），如果相等，则p[k]=p[j]，满足情况1。若不相同，即模式串第k位发生失配，移动到k'=next[k]位继续进行比较。返回情况1或者2。如果next[k]=-1（仅第1位的next[0]的值为-1），说明j+1的前一位j与第一位比较仍然不等，那应该让第j+1位直接与第1位（下标为0）进行比较。
　　next[k+1]的计算依赖于next[k]，next[k+1]仅有一种方式获得，即第k+1字符的前面k个字符完全匹配（或者前一元素与第一个元素仍然不匹配）。而next[k]是已经计算的，即next[k]可以保证第k字符的前面k-1个字符（除了第k个字符）完全匹配，而且该字串是最长字串。因为只需比较第k个字符是否匹配。匹配成功即情况一，匹配失败则继续寻找next[next[k]]。
　　编程时，每次进行计算next[j+1]时，必须保证j与k呈对应关系，即每新一次计算前，next[j]=k（next[j+1]=k+1，因而也可以写成next[++j]=++k）。

KMP算法的再改进

　　当第k+1位发生失配时，根据原算法，可以找到一个子串，与之匹配。此时，next[j+1]=k+1
但若 T[j+1]= T[next[j+1]]=T[k+1]，则当T[j+1]发生失配时，程序会使回到第next[j+1](=k+1)位，与T[j+1]所对应的主串字符进行比较。但由于主串字符已经不等于T[j+1]，因而也必然不等于T[next[j+1]]，因而此次比较必然失败。
　　改进：当T[j+1]= T[next[j+1]]=T[k+1]时，next[j+1]= next[next[j+1]]=next[k+1]，从而避免不必要的重复比较。

附：
普通模式匹配算法代码：
int mystrstr(char* S, char* T, int pos)
{
    int i=pos; //设置主串的指针位置（初始位置为给定的开始位置）
    int j=0; //设置子串的指针位置（初始位置为子串的首元素）
    
    while (S[i]!='\0')
    {
          if (T[j]=='\0') {return (i-j+1);} //比较到子串的’\0’，匹配成功
          if (S[i]==T[j]) {
             i++;
             j++;
            //子串与主串在该位的匹配值相等，则继续比较下一字符
          } else { //若不相同
            i=i-j+1; //主串回退到本次比较开始字符的下一字符 
            j=0; //模式串回退到首字符
          }
    }
    return 0; 比较到主串的’\0’，且此时子串的比较位不等于’\0’，匹配失败
}

KMP主程序代码：
int mystrstr(char* S, char* T, int pos, const int* next)
{
    int i=pos; //主串指针 
    int j=0; //模式串指针 
    
    while (S[i]!='\0') //当主串指针所指字符不为'\0'时,继续比较 
    {     
          
          if (j==-1) {i++;j++;}
          // 当头元素仍然不匹配时,j=-1,此时j指针清0指向模式串的首元素, i指针指下主串的下一元素 
          if (T[j]=='\0') {return (i-j+1);}
          // 当模式串指针所指元素为'\0'时,匹配完成,返回位置 
          if (S[i]==T[j]) {
             i++;
             j++;
             //当模式串指针与主串指针所指元素相同时,两指针都相加.比较下一元素 
          } else {
            j=next[j];
            //若模式串指针与主串指针所指内容不同时,模式串指针回退指到next[j]位置(第j位发生失配) 
          }
    }
    return 0;
}

生成next[]数组代码
//该程序用next[i]来推测next[i+1]
//每次比较开始时next[i]=k,每次比较开始前i与k成对应关系 
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1; //k为当第j位发生失配时,需要移动到的下一次进行比较的位(第k位)            
     next[0]=-1;
     //给定初始值,当比较到第一个元素(下标为0)仍然不等时,k的值为-1 
     
     while (j<strlen(T)) //j的大小有strlen(T)个,下标从0开始 
     {
           if (k==-1||T[k]==T[j])
           {
              //next[j]=k的定义为: t[0]...t[k-1]=t[j-k+1]...t[j-1] 
              //当T[k]=T[j]时,即T[next[j]]=T[j]时,T[1]...T[k]=T[j-k+1]...T[j],此时next[j+1]=next[j]+1=k+1,即可以求出next[j+1] 
              //当k=1时,即j+1的前一个元素与模式串的首元素相比,仍然不同,则应该让第j+1个元素直接与首元素进行比较 
              next[j+1]=k+1;
              j++; 
              k++; //k=next[j+1]=k+1,不能写k=next[j+1],因为上面一句j已经变化过了
              //next[j+1]=next[j]+1=k+1,即j+1与k+1是成对出现的 
              //下次比较开始前,j与k必须成对应关系出现, 满足这个式子：next[j+1]=k+1
           } else {
               k=next[k];
               //如果不等,可以理解为模式串的第k(next[j])位发生不匹配
               //则寻找到第next[k]位(保证k之前的元素匹配)继续进行比较
               }
     }
}

生成KMP改进算法的next[]数组代码
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1;

     next[0]=-1;
     // next[j]=k
     
     while (j<strlen(T))
     {
           if (k==-1||T[k]==T[j])
           {
              next[j+1]=k+1;
              
              if (T[j+1]==T[next[j+1]]) {
                 next[j+1]=next[next[j+1]];
              } 
              //就多了这段，当T[j+1]与T[next[j+1]]相等时，使next[j+1]=next[next[j+1]]
              j++;
              k++;
           } else {
               k=next[k];
               }
     }                 
}


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/ultrasurf/archive/2007/11/08/1873589.aspx