KMP详解

时间：2024-01-21 09:19:41

KMP详解

引入

    字符串有一种基本的操作，叫做查找。当你在淘宝上搜索时，就是在查找；当你在百度上搜索时，也是在查找；当你在点子字典上输入一个英文单词的时候，也是在查找。

    在C++的string库中有一个查找的函数，即str1.find(str2).其中，str1指的是被查找的母串，str2指的是要查找的子串。例如下面一段程序

string str1="Hello World";
string str2="Hel";
printf("%d", str1.find(str2));

 

 

 

     这个程序的返回值是0.也就是说，str1.find(str2)返回的是str2在str1中第一次出现的位置。

注意事项

    在开始之前，我们约定一下几个事项：

  •     母串表示被查找的字符串，用strmo表示
  •     子串表示要查找的字符串，用strch表示
  •     我们用i来表示strmo中的第i个字符，用j来表示strch中的第j个字符，使读者更容易理解。

古老的字符串查找方法

    暴力的字符串查找方法就是直接模拟人的思想，不断地在母串中一个字符一个字符地查看与子串是否匹配，直到匹配成功或母串结束为止。　　

find(String strmo, String strch)
{
    int M=strmo.length();
    int N=strch.length();
    for(int i=0;i<=N-M;i++)
    {        
         int temp;
         for(j=0;j<M;j++)
              if(strch[i+j] != strmo[j])
	      {
		  temp=j;
                  break;
              }
          if(j == M)
              return i;
    }
}

 

 

 

 

 很明显，这个算法的复杂度为O(NM)

KMP的前身——有限状态自动机

简介

    有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。

　　有限状态自动机由

　　　　　 – Q——状态的非空有穷集合。∀q∈Q，q称为M的一个状态。
　　　　– Σ——输入字母表。
　　　　– δ——状态转移函数，有时又叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。
　　　　– q0——M的开始状态，也可叫作初始状态或启动状态。q0∈Q。
　　　　– F——M的终止状态集合。F被Q包含。任给q∈F，q称为M的终止状态。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——百度百科

    你看懂了吗？

　　最重要的是第二段的五元组，

　　下面我们将结合图形来具体分析

图例

　　如图，这就是一个无限状态自动机的例子。

　　在每一条带有箭头的线上有着0或1的数字，Sn指向Sm，上面数字为x表示当Sn遇到x时状态变为Sm

　　你会神奇的发现，所有的圆（也就是状态）都只有一个圆，但是其中一个时同心圆，这代表当遇到这个状态时就结束了。

    起点的代表就是S1,因为指向S1的箭头中有一个是没有任何状态进入的。

    这个有限状态自动机能够识别许多数，这些数只要满足：从起点出发，不断转移状态，直到遇到终点（注意！只要遇到终点就停止，无论后面还有没有输入）为止，那么这一个输入就识别成功了。

    对于样例来说，001这个输入是可以被识别的，1001也是可以被识别的，1001101也是可以被识别的。

有限状态自动机和子串查找的关系

    有限状态可以看为对于一个母串的有限状态自动机，将子串读入，如果可以被母串的有限状态自动机识别，那么就说明在母串中有一个与子串相同的字符串。这样解释可能有些难懂，我们举例来说明。

    对于一个子串为ABABAC的字符串，它的有限状态自动机如下：

那么对于一个母串：ABCABABCCCABAABABABABAC，它是可以被输入成功的，它的状态变化标示为：

0-1-2-0-0-0-1-2-3-1-2-3-4-5-4-5-6

所以，这个母串是可以被读取的。

如何构造有限状态自动机

对于上面的例子，我们看图看起来很简单，但是机器是怎么操作的呢？

我们用一个DFA数组来储存一个状态，DFA[i][j]=x表示当在第i个状态，读取j时，变化为j状态。

那么如何生成DFA数组呢？

首先将第一列，也就是DFA[][0]初始化为0，然后将dfa[strch[0]][0]=0；

对于接下来的所有i列，克隆第x列（每个i都有一个对应的x），然后dfa[strch[j]][j]=j-1;

这个x的生成，就是X=dfa[strch[j]][X],至于具体是怎么得到的，在书中并没有提及，这里留下一个疑问

下面就是生成DFA数组的代码：

 

dfa[strch[0]][0] = 1;
for(int X=0,j=1;j<M;j++)
{
    for(int c=0;c<R;c++)
        dfa[c][j] = dfa[c][X];
    dfa[strch[j]][j] = j+1;
    X = dfa[pat.charAt(j)][X];
}

 

 

 现在的KMP

 通常来说，机器人在查找匹配的字符串的时候，是一个一个搜索的，但是人类的思维更快，为什么呢？以一个图为例。

机器人在不断匹配时，发现有不匹配的情况，那么将i移回第一位，将j移到第0位

但是我们在用肉眼进行匹配的时候，i会跳到下一个i的地方，进行匹配，这样就可以使得整个算法的复杂度是线形的，就是O(n+m),其中，n表示母串长，m表示子串长。

    简单来说，KMP就是利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。

         那么我们是如何知道j要调到哪里的呢？这就要通过next数组来实现了。

    当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。那么也就

是：

　　strch[0 ~ k-1]==strch[j-k ~ j-1]

如果不明白，可以参考下面的图：

　　那么如何求这个k呢？这就需要讲到一个数组——next数组。

　　因为每一个位置的j都有可能不匹配，所以我们需要将所有的j对应的k全部保存下来，记录在next数组里面，所以next数组保存的就是当一个位置的字符匹配失败的时候，应该挪到的下一个位置

　　　　·当j=0且不匹配时，j不挪动，而i移动至下一个位置。所以next[0] = -1

　　　　·当j=1且不匹配时，j只能挪到第0个位置，也就是next[1]=0;

　　　　·其余情况，当strch[k]==strch[j]时，next[j+1]==next[j]+1

　　　　·当strch[k]!=strch[j]时，k=next[k]

　　所以整一份的kmp模板就是：

void GetNext(char* strch,int next[])  
{  
    int Len = strlen(strch);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j<Len - 1)  
    {  
        //strch[k]表示前缀，strch[j]表示后缀  
        if (k==-1 || strch[j]==strch[k])   
        {  
            k++;  
            j++;  
            next[j]=k;  
        }  
        else   
            k=next[k];  
    }  
}  

bool kmp(char *strmo,char *strch)
{
    int i=0,j=0,len0=strlen(strmo),len1=strlen(strch);
    while(i<len1&&j<len0)
　　{

        if(i==-1||strmo[i]==strch[j]) 
　　　　{

　　　　　　i++;
　　　　　　j++;
　　　　}
        else 
　　　　　　j=next[j];
　　}
    return i==len1;
}

int kmp_len(char *strmo,char *strch){
    int i=0,j=0,maxlen=0,len0=strlen(strmo),len1=strlen(strch);
    while(i<len1&&j<len0)
　　{

        if(i==-1 || strmo[i]==strch[j]) 
　　　　{
　　　　　　maxlen=max(++i,maxlen);
　　　　　　j++;
　　　　　}
        else 
　　　　　　j=next[j];
　　}
    return maxlen;
}

 

posted on 2018-08-20 18:41 绝境狼王 阅读(...) 评论(...) 编辑 收藏

相关文章