欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP

程序员文章站 2022-07-14 08:23:20
...

KMP

KMP

题意:

给你字串和母串,让你找出字串在母串中第一次出现的位置,若不存在则输出-1.

思路:用KMP求解

代码:

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1e6+10;
int T,n,m,s[maxn],t[maxn],nxt[maxn];

void getnxt()
{
	int i=1;
	int j=0;
	nxt[0]=0;
	while(i<m)
	{
		if(t[j]==t[i])
		{
			nxt[i++]=++j;
		}
		else if(!j)
		{
			i++;
		}
		else
		{
			j=nxt[j-1];
		}
	}
} 

int kmp()
{
	int i=0;
	int j=0;
	while(i<n&&j<m)
	{
		if(s[i]==t[j])//子串和母串中的这个位置的值相同
		{
			i++;
			j++;
		}
		else if(!j)
		{
			i++;
		}
		else//若此时两个值不同,则j跳回
		{
			j=nxt[j-1];
		}
	}
	if(j==m) return i-m+1;
	else return -1;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
		for(int i=0 ;i<n ;i++ )scanf("%d",&s[i]);
		for(int i=0 ;i<m ;i++ )scanf("%d",&t[i]);
		getnxt();
		printf("%d\n",kmp());
	}
	return 0;
}

 

相关标签: KMP