深度解读KMP算法

/*
深度解读KMP算法：
    一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。 -KMP
    
    KMP算法常用于字符串间的匹配问题
    
    给定主串S和模式串P,S的长度为n，P的长度为m，在主串P中寻找模式串S出现的位置
    （为方便理解S和P的下标均从1开始）
    
    在解读KMP算法之前让我们先了解暴力枚举的做法：
    
    依次枚举主串S中下标为1,2,3,...n-m+1的位置，
    将其作为比较的起点依次与模式串P进行匹配，
    若匹配成功则记录位置，匹配失败则换下一位进行匹配
    
    在上述匹配过程中，每一次失败的匹配都没有为我们提供丝毫的经验，
    我们还是如同第一次匹配一样去麻木的从下一位开始匹配，这显然是不太聪明的做法，
    所以穷举的时间复杂度是O(mn)的。
    
    接下来进入KMP的正题：
    
    KMP其实就是一个不断提取失败经验的过程，每一次不成功的匹配都为它的下一次匹配积累了经验
    
    接下来考虑这样一种情况：
                                  1 2 3 4 5 6 7 8 9 10 11 12
                        主串S     c a l g o a i t m n  t  g
                        
                      模式串P       a l g o a e
                                    1 2 3 4 5 6
            
        用s[i]和p[j]来表示正在匹配的字符，则我们会发现模式串的前5个字符都匹配成功了，
        只有最后一个字符没有匹配成功，此时，我们的 i = 7,j = 6
        
        接下来就是KMP的精髓：跳过不可能成功的尝试
        
        在上述失败的匹配过程中我们获得了如下信息：
        在主串的i = 7的位置之前的5个字符和模式串P的前5个字符是正确匹配的
        假设我们手动模拟的移动模式串P,我们会发现移动的前4步都是不可能成功的，
        唯有当模式串的某一段前缀(下列中为模式串中j=1处的a)和i=7之前的某一段后缀(下列中为主串中i=6处的a)匹配时，我们才有可能匹配成功
                        
                        主串S      1 2 3 4 5 6 7 8 9 10 11 12
                                   c a l g o a i t m n  t  g
                                             
                      模式串P        a l g o a  e
                                     1 2 3 4 5  6
        
        而因为模式串P的前5位都正确匹配了，
        所以i = 7的某一段后缀同样是包含于模式串P中的
        
        所以容易得知这里的前缀和后缀都是包含于模式串P中的，
        而基于贪心的匹配原则，我们自然希望模式串P的前缀和后缀匹配的越多越好
        
        由此我们引入模式串P的一个关键因素next数组
        next[i]存储的是在模式串P的前i个字符中，前缀和后缀的最大匹配程度
        (其中前缀和后缀不能相等，因为模式串P当然最大匹配自己，但这没有对解决问题没有任何意义)
        
        下面我们举一个形象的例子：
            假设模式串P是    a b c a b d
            则我们可以得到
                           next[1] = 0;
                           next[2] = 0;
                           next[3] = 0;
                           next[4] = 1;
                           next[5] = 2;
                           next[6] = 0;
        
        相信你已经熟悉了next数组的含义，接下来让我们模拟一下KMP匹配字符串的过程
        假设在主串S中模式串的前j1位均已经匹配，但其j1+1位和S串中的第i位并不匹配,
        这时我们并不急于跳到下一个i的位置，而是尝试寻找一个新的j2的位置，
        使得此时已经匹配好了若干元素，而不是象暴力枚举一般每次从零开始，
        我们并不是从0开始的，按照next数组的定义，
        我们是在已经匹配好了模式串的next[j1]位的情况下，
        将模式串中的j2 = next[j1]+1 的位置和i再进行匹配判断的
        
        通过上述匹配过程中不断寻找曾经的自己，我们的匹配过程便得到了大大的加速和优化
        
        而获取next数组的过程我们则只需要让主串和模式串P相同再进行匹配和记录即可轻松获取
        
        下面是代码实现部分：
*/

#include <iostream>

using namespace std;

const int N = 100010,M = 1000010;

char p[N],s[M];
int ne[N];
int n,m;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>p+1;
    cin>>m>>s+1;
    
    //求next数组
    ne[1]=0;//此步可省略，但为了便于理解，没有省略
    //错开一位匹配，是为了更好的试探
    for(int i=2,j=0;i<=n;i++)
    {
        //当退无可退时，或者寻找到了最大匹配时退出
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;//若成功则匹配程度+1
        ne[i]=j;//记录最大前后缀匹配程度
    }
    
    //正式开始匹配,仍然错开一位，方便试探
    for(int i=1,j=0;i<=m;i++)
    {
        //当退无可退时，或者寻找到了最大匹配时退出
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n)//当成功匹配最后一位时，输出结果
        {
            //题目要求下标从0开始，需注意
            cout<<i-n<<" ";
            j=ne[j];//找完后找下一个匹配
        }
    }
    return 0;
}