在两个字符串S[i]与T[j]中i可以不回溯，模式向右滑动到新比较起点k，并且k仅与模式串T有关。

因此可以先看一下我之前通过看网课写的一篇KMP算法的基本解释

令k=next[j]，则：

next[j]=-1（j==0）

next[j]=max{k|0<k<j且T0…Tk-1=Tj-k+1…Tj-1}

next[j]=0(其他情况)

next[j]函数象征着模式T中最大相同前缀字串和左字串的长度。

这里有个很好的小例子




next[j]的算法分析


k=next[j-1];

while(k!=-1)&&(t[k]!=t[j-1])

k=next[k];

next[j]=++k;

next[j]的算法分析：

k=next[j-1]（由next[的定义可以知道：t0t1…tk-1=tj-k…tj-3tj-2）

1.如果t[k]t[j-1]或k-1（不存在长度相同的前缀字串和左字串）

则则t0t1…tk-1tk= tj-k…tj-3tj-2tj-1，因此

next[j]=k+1，next[j]计算结束

否则， 查找t0t1…tk的最长左子串

k=next[k]，转 1 继续执行



否则查找t0t1…tk的最长左字串

k==next[k]，转1继续执行





1.   在串S和串T中分别设比较的起始下标i和j；

2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕

2.1 如果S[i]==T[j]，继续比较S和T的下一个字符；否则

2.2 将j向右滑动到next[j]位置，即j=next[j]；

2.3 如果j=-1，则将i和j分别加1，准备下一趟比较；

3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回-1；

基本思想：
从主串S的第0个字符开始和模式T的第0个字符进行比较，若相等则继续比较两者的后续字符；

否则，从主串S的第一个字符开始和模式T的第0个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明比较失败。



1.在串S和串T中设比较的起始下标I和j；

2.循环知道S或T的所有字符比较完；

2.1如果s[i]==T[j]，继续比较S和T的下一个字符；

2.2否则，将i和j回溯（i=i-1，j=0），准备下一趟比较；

3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标（i-j）；否则匹配失败，返回-1；

代码实现如下



设串S的长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况。

（1）最好：不成功的匹配都发生在串T的第一个字符。

所有匹配成功的情况可能有n-m+1种

最坏情况：不成功的匹配都发生在串T的最后一个字符。

为什么BF算法的时间性能低？

在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。

如何在匹配不成功的时候主串不回溯？

主串不回溯，模式就需要向右滑动一段距离。

因此KMP算法很好的解决这个问题

描述

求一个字符串在另一个字符串中的位置，称为模式匹配，如果匹配成功，则输出第一次匹配成功的位置，否则输出0。KMP算法是一种高效的模式匹配算法。要求采用KMP算法完成该题目。


输入

输入包今含若干个测试用例，每个测试用例占两行，其中第一行为目标字符串，第二行为模式串。

输出

对每个测试用例，用两行输出，其中第一行输出该用例的模式串的各字符的next值，第二行输出模式串在目标串中第一次匹配成功的位置。如果匹配不成功，则输出0。

样例输入

abcdefg

bcd

0000001

0001

110011001100

111

dabcabcabc

abc




样例输出

0 1 1

2

0 1 2 3

4

0 1 2

0

0 1 1

2
#include<iostream>
#include<cstring>
using namespace std;
string s1,s2;
int next[50]={0};
void Next(string s2)
{
    int k=3,j,i;
    next[1]=0; next[2]=1;
    while(k<=s2.size()){
    j=k-1; i=next[j];
    while(j-1&&s2[j-1]!=s2[i-1]){
    j=i;
    i=next[j];
    }
    next[k]=i+1;
    k++;
    }
}
int Index_KMP(string s1,string s2)
{
    int i=1,j=1;
    while(i<=s1.size()&&j<=s2.size()){
        if(s1[i-1]==s2[j-1]||j==0){i++;j++;}
        else j=next[j];
    }
    if(j>s2.size())return i-j+1;
    return 0;
}
int main()
{
    int i;
    while(cin>>s1>>s2)
    {
        i=1;
        Next(s2);
        while(i<s2.size())
        {
            cout<<next[i++]<<" ";
        }
        cout<<next[i]<<endl;
        cout<<Index_KMP(s1,s2)<<endl;
    }
    return 0;
}

BF 算法：

#include<stdio.h>
#include<string.h> 
#include<stdlib.h> 
#define MaxSize 100 //串的最大长度 
//串的定长顺序储存结构 
typedef struct//
{  
    char str[MaxSize];//储存串的一维数组 
}SString;    
int BFIndex(SString S, int pos, SString T) 
{    
    int i = pos;   
    int j = 0; //初始化 
    while(i <=strlen(S.str)&& j<=strlen(T.str)) //两串均未达到串尾 
    {   
	    if(S.str[i-1] == T.str[j])//继续比较后续字符 
	    {
	           i++;   
			   j++;   
		}   
		else   //指针后退重新开始匹配 
		{   
		   i = i-j+1;    
		   j = 0;  
		}  
	}   
	if (j==strlen(T.str))//匹配成功 
   {      
       return (i-strlen(T.str));   
   }  
    else    //匹配失败 
	return 0;
}

int main() 
{  
     SString S,T;  
     int pos,ans;  
     printf("请输入主串S的字符:");  
     scanf("%s",S.str);      
     printf("请输入子串T的字符:");  
     scanf("%s",T.str);  
     printf("请输入pos的值:");  
     scanf("%d",&pos);      
     ans=BFIndex(S,pos,T);//调用BFIndex函数 
     printf("子串T在主串S中第pos个字符之后的位置为:"); 
     printf("%d\n",ans);    
     system("pause");  
     return 0;
}




KMP算法
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define MAXLEN 100//串的最大长度 
typedef struct
{
	char ch[MAXLEN+1];
}SString;
void get_next(SString T,int next[])//求模式串next函数值 并存入数组next 
{
	int i,j;
	i=1;
	next[1]=0;
	j=0;
	while(i<strlen(T.ch))
	{
		if(j==0||T.ch[i]==T.ch[j])
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}
int Index_KMP(SString S,SString T,int pos,int next[])
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置 ，其中T非空 
{
	int i,j;
	i=pos;j=1;
	while(i<=strlen(S.ch)&&j<=strlen(S.ch))
	{
		if(j==0||S.ch[i]==T.ch[j])
		{
			++i;++j;
		}
		else
	    {
	    	j=next[j];
		}
	}
	if(j>strlen(T.ch))
		return i-strlen(T.ch);
	else
		return 0; 
}

int main()
{
	SString S,T;
	int pos,ans,next[MAXLEN];
	printf("请输入S串\n"); 
	scanf("%s",S.ch);
	printf("请输入T串\n");
	scanf("%s",T.ch);
	printf("请输入pos的值\n");
	scanf("%d",&pos);
	get_next(T,next);
	ans=Index_KMP(S,T,pos,next);
	if(ans==0)
	  printf("匹配失败\n");
	else
	{
		printf("模式T在主串S中第pos个字符开始第一次出现的位置为:%d\n",ans);
	}
}



KMP扩展：
void get_nexttval(SString T,int nextval())
{
	int i,j;
	i=1;
	nextval[1]=0;
	j=0;
	while(i<T.length)
	{
		if(j==0||T.ch[i]==T.ch[j])
		{
			++i;++j;
			if(T.ch[i]!=T.ch[j])
			  nextval[i]=j;
			else nextval[i]=nextval[j];
		}
		else
		    j=nextval[j];
	}
}