KMP算法实现字符串匹配

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;

int main()
{
    string str,p;
    cin>>str>>p;
    int n=str.length();
    int m=p.length();
    
    //compute prefix function
    int pre[100];
    pre[0]=-1;
    int k=-1;
    for(int j=1;j<m;j++)
    {
       while(k!=-1&&p[k+1]!=p[j])//这里刚开始用if，现在用while，这是为什么呢？ j往后退，寻找新的可能性
       {
          k=pre[k];
       }
       if(p[k+1]==p[j])
       {
          k=k+1;
       }
       pre[j]=k;
    }
    for(int i=0;i<m;i++)
    {
       printf("%d ",pre[i]);
    }
    int j=-1;
    for(int s=0;s<n;s++)
    {
        while(j!=-1&&p[j+1]!=str[s])
           j=pre[j];
        if(p[j+1]==str[s])
           j++;
        if(j==m-1)//当j到达m-1时候，字符串就已经匹配成功了
        {
           printf("Match!
");
           //break;
           j=-1;//multi match ，如果允许已经匹配的字符串重叠呢？
        }
    } 
    printf("
");
    getchar();
    getchar();
    return 0;
} 

Question: 字符串A是否是字符串B的字串？

A: KMP算法

资料: http://www.ituring.com.cn/article/59881 讲得很透彻

http://www.matrix67.com/blog/archives/115 原创讲解

http://mindhacks.cn/2011/07/10/the-importance-of-knowing-why-part3/ 为什么学算法这么难？

KMP算法主要是前缀函数的计算

前缀函数的计算就是计算某一长度的字符串，首位相同的字符串有多少(不是对称)。这方便在不匹配的时候j回退到什么地方；

计算函数就外层遍历所有字符串，发现不对的时候就把J回退回去j=next[j]，这是循环进行的，如果还是不匹配还是往回退，知道一个字符都没有匹配了，重新开始了为止。