KMP与有限状态自动机

- 关于字符串s的next数组的求解,next数组本质是当j+1位匹配失败时j应当回退到的位置
1.初始化next数组，令j = next[0] = -1;
2.令 i = 1，2，... len-1(len为s的长度)，对每个i,通过步骤3和4求解next[i]
3.s[i] == s[j+1] 成立或者令j = next[j],直至j回退至-1
4.如果s[i]==s[j+1], 则令next[i]=j+1,否则next[i] = j.

KMP算法:
判断pattern串是否为text串的子串。

求出pattern串的next数组
初始化j = -1,j表示pattern串中已经匹配的最后位。
令 i=1，2，...n-1(n为text的长度)，对每个i执行以下步骤4和5来匹配text[i]和pattern[j+1]
text[i]==pattern[j+1],或者令j=next[j],直至j回退到-1

如果text[i]==pattern[j+1]，则令j++,如果j==m-1(m为pattern的长度)则表示pattern是text的子串，返回true

bool strStr(string text, string pattern) {
      // pattern串为空时 此处默认是text的子串
      if(!pattern.size()) return true;
      // 求解pattern串的next数组
      vector<int> next = getNext(pattern);
      int j=-1; //j指向pattern中已经匹配的最后一位
      // kmp算法
      int n = text.size();
      int m = pattern.size();
       // 遍历i 匹配text[i]与pattern[j+1]
      for(int i=0;i<n;++i)
      {
          while(j!=-1 && text[i]!=pattern[j+1])
              j = next[j];
          // 匹配成功 令j+1
          if(text[i]==pattern[j+1])
              ++j;
          // pattern完全匹配 说明是text的子串 返回true
          if(j==m-1) return true;
      }
      return false;     
  }
  // 获取pattern串的next数组
  vector<int> getNext(string s)
  {
      int len = s.size();
      vector<int>next(len);
      //初始化j=next[0]=-1
      int j = -1;
      next[0] = -1;
      // 求解next[1]~next[len-1]
      for(int i=1;i<len;++i)
      {
          while(j!=-1 && s[i]!=s[j+1])
          {
              j = next[j]; // 反复令j = next[j]
          }
         // 直到j回退到-1 或是s[i]==s[j+1]
         // 如果是s[i]==s[j+1]  则next[i]=j+1,先令j指向这个位置
          if(s[i]==s[j+1])
              ++j; 
          next[i] = j;
      }
      return next;
  }

其他变形问题。如求pattern串在text串中第一次出现的位置；pattern串在text中出现的次数（每成功匹配一次让计数器增1，j回退到next[j]）等等。

从DFA的角度看待KMP问题

在文本串s中查找模式串p的过程就是在状态转移的过程。利用模式串p构造出有限状态自动机，要确定状态转移的行为关键点有两个：
1.当前所处状态
2.当前遇到的文本串s中的字符
KMP算法使得当匹配失败时，可以不回退文本串的指针，而将模式串的指针回退到适当位置（重启状态X）。

具体地，

构造一个二维的dp数组来描述状态的转移图：
dp[j][c] = next
0<=j<=M，代表当前的状态
0<=c<256，代表遇到的字符（ASCII码值）
0<=next=M，代表要转移到的下一个状态
例如 dp[4]['A'] = 3 表示当前是状态4，如果遇到字符'A'，则模式串p应当转移到状态3
利用该状态转移过程，KMP算法的search函数可以写成：

int search(string txt, string pat)
{    
    //模式串的长度
    int M = pat.size();
    //文本串的长度
    int N = txt.size();
    //pat的初始状态为0
    int j = 0;
    //扫描文本串
    for(int i=0;i<N;++i){
        //当前状态是j,遇到字符txt[i]
        //pat应该转移到哪个状态?
        j = dp[j][txt[i]-'0'];
        //如果到达终止态 说明匹配成功 返回匹配开头的索引
        if(j==M) return i - M + 1;
    }
    //未到达终止态 匹配失败
    return -1;
}

状态转移数组dp如何构造的？（同样是利用dfa）

    //模式串长度
    int M = pat.size();
    int dp[M][256];
    //base case
    dp[0][pat[0]-'0'] = 1;
    //重启状态 当匹配失败就回退到重启状态
    int X = 0;
    //当前状态j从1开始
    for(int j=1;j<M;++j){
        for(int c=0;c<256;++c){
            //匹配成功进入下一个状态
            if(pat[j]-'0'==c)
                dp[j][c] = j+1;
            //否则回退到重启状态
            else dp[j][c] = dp[X][c];
        }
        //更新重启状态
        X = dp[X][pat[j]-'0'];
    }

给个例子测试一下：

#include<bits/stdc++.h>
using namespace std;

//构造状态转移dp数组
void helper(string& pat, vector<vector<int>>& dp)
{
    int M = pat.size();
    dp[0][pat[0]-'0'] = 1;
    int X = 0;
    for(int j=1;j<M;++j){
        for(int c=0;c<256;++c){
            if(pat[j]-'0'==c)
                dp[j][c] = j+1;
            else dp[j][c] = dp[X][c];
        }
        X = dp[X][pat[j]-'0'];
    }
}

//在文本串txt中查找模式串pat
int search(string& txt, string& pat, vector<vector<int>>& dp)
{
    int N = txt.size();
    int M = pat.size();
    int j = 0;
    for(int i=0;i<N;++i){
        j = dp[j][txt[i]-'0'];
        if(j==M) return i-M+1;
    }
    return -1;
}

int main()
{
    string txt = "AABRAACADABRAACAADABRA";
    string pat = "AACAA";
    int M = pat.size();
    vector<vector<int>>dp(M,vector<int>(256,0));
    helper(pat,dp);
    int index = search(txt,pat,dp);
    cout<<index<<endl;  //12
    return 0;
}