(K)MP有限状态自动机

模式匹配自动机

什么是有限状态自动机？
定义 n 个不同状态，记为 {1,2…n}，在状态 i 时输入 s，达到状态 j，记为 goto (i,s)=j
对于字符串 s 而言，在一个状态 i 下输入一个字符 ch，也会达到一个指定状态 ：
假定新的状态为串 s [1,i]+ch 的最长相等前后缀 ，便能够用这个状态机模拟 KMP 算法匹配字符串的过程。
当字符集仅为 a、b 时，有：

其中 goto (4,a)=3，也就是说 abab+a 的最长相等前后缀 对应的状态是状态 3 ，也即表示字符串 “aba” 的状态。
似乎这样就足够了。
我们获得了 goto 函数，定义为：

goto (Si,a)：串 s [1,i] a 的最长相等前后缀。

为了得到这个 goto 函数的值，我们需要定义 fail 函数：

fail (Si): 串 s [1,i] 的最长相等前后缀。

因为得到 goto (i,a) 的前提是，知道 s [1,i] 的最长相等前后缀 s\[1,j] ：若 s [j+1] 与 a 相同，则 goto (i,a)=j+1，否则求 s [1,j] 的最长相等前后缀，直到长度为 0。
为了表示 “s [j+1] 与 a 相同” 这一条件，定义函数：

follow (Si, a): 状态 Si 输入 a 后，来到下一个状态。

对于字符串 abcde，follow (0,a)=1,follow (1,b)=2,follow (2,c)=3… 以此类推，而其他值未定义。
到这里，goto 函数就可表示为：

state go_to(state s,char ch){

    while(follow(s,ch)未定义)
    {
        s=fail[s];
    }
    return follow(s,ch);
}

若 s 为模式串的状态，ch 为 s 的后继字符，则这一 goto 值可当做新的 fail 值。

未定义状态，比如 follow (0,b), 计为 0 可不可行？
与之配套地，fail (0), 计为 0，也就是说空串的最长相等前后缀长度 为 0。
若 fail (0) 记为 - 1，则 follow (s==-1,ch) 将陷入故障状态：没有状态被记为 - 1。
问题出现了！函数不得不进入死循环：因为 s 一直为 0。
破环方式也很简单：

引入状态 - 1，未定义状态记为 - 1，fail (0)=-1，follow (-1, 任何字符)=0。

这样，当计算 ab+c 的最长相等前后缀 时，便能够得到 go_to (2,c)=0。
类似地，计算fail数组的函数为：

Compute_fail()
{
    fail(s0) = ⊥;
    s = s0;
    for( i =1 to |P| ){
        s = goto(s, P[i]);
        fail(si) = s ;
    }
}

goto 和 fail 数组的关系：fail 反映模式串中的某部分字符串的最长相等前后缀 ，goto 反映文本串和模式串的匹配情况。诚然，fail 数组可以通过 goto 函数得到，但记录一些中间状态有利于加速算法。

匹配函数：

Match(t)
{
    s= s0;
    for(int i=1 to |T|){
        if( s 是终止状态 )
           return 匹配!
        else  
            s=goto(s,T[i]);
    }
} 

MP 有限状态自动机

我们都知道 mp 的 c++ 写法。
基于以上定义，我们艰难地知道 mp 的有限状态自动机写法：

#include<bits/stdc++.h>
using namespace  std;
#define state int
string P; //模式串
string T;
state fail[1000005];
state edge[1000005][26];

state follow(state s,char ch){
    if(s==-1) return 0;
    if(edge[s][ch-'A']==s+1) return s+1;

     return -1;
}
state go_to(state s,char ch){

    while(follow(s,ch)==-1)
    {
        s=fail[s];
    }
    return follow(s,ch);
}

void get_fail(){
    fail[0]=-1;
    state s_=0;
    for(int i=1;i<P.size();i++){
        s_=go_to(s_,P[i]);
        fail[state(i)]=s_;
        
           if(fail[s_]!=-1&&P[s_+1]-'A'==P[i+1]-'A'){
            fail[state(i)]=fail[s_];
        }//！！！K优化！！！
        
        edge[i-1][P[i] - 'A'] = i;
    }
}
void match(){
    state s_=0;
    for(int i=1;i<T.size();i++){
        s_=go_to(s_,T[i]);
        if(s_==state(P.size()-1)){
            cout<<i-P.size()+2<<endl;

        }
    }
}
signed main() {

    cin>>T>>P;
    P=" "+P;
    T=" "+T;

    get_fail();

    match();

for(int i=1;i<P.size();i++){
    cout<<fail[i]<<" ";
}

}

洛谷提交情况如下： 洛谷
这是一种没有任何实战意义的写法。
需要注意俩点：

if(edge[s][ch-‘A’]==s+1) return s+1;

只有计算 fail 函数时，遍历过某个字符时，才连一条 edge 边。
也就是说，在未遍历时，字符串 abc 的 follow (0,a)=-1,follow (1,b)=-1,follow (1,c)=-1, 而当遍历过 b 时，follow (0,a)=1,follow (1,b)=2,follow (1,c)=-1。这样做的原因是，若模式串天然有 follow 边，则 fail 数组的值会依次为 - 1,1,2,3,4…

if(fail[s_]!=-1&&P[s_+1]-‘A’==P[i+1]-‘A’){
fail[state(i)]=fail[s_]; }

这是 knuth 优化。对于字符串 aaaa，mp 的 fail 数组是 0,1,2,3 而 kmp 的 fail 数组是 0,0,0,3。
因为 kmp 的 fail 数组不能很好地反映字符串的前后缀的关系，而我们通常需要利用这种关系，故现常用 mp，且把 mp 称为 kmp。

MP 算法是一个 O (m+n) 的算法，证明如下：

1. 在 check 函数中，对文本串扫描一遍，无回头扫描，消耗 O (n)
2. 自动机向右的移动距离 >= 向左移动的距离 >= 调用 fail 的次数，而向右的移动距离 = 对文本串扫描的距离 = n，故调用 fail 的次数 = O (n)
3. 构造 fail 数组时，向右的移动距离 = 对模式串扫描的距离 = m，即 Fail 构造复杂度的复杂度为 O (m)

综合为 O (m+n)。实际上，除了 aaab 匹配 aaaaaaaa 这种极端数据外，mp 和暴力算法复杂度接近：随机情况下，暴力的复杂度也接近 O (m+n)，在数据随机生成的情况下，暴力匹配也基本很快就会失配。