HDU-1711-Number Sequence(数组跑KMP)

个人博客

题目链接

题意：

给你两个数组的所有元素，让你对它们进行匹配，当位置为多少时候它们能完全匹配。

题解：

直接跑KMP就可以了，唯一注意的…emmm…应该不用注意吧，也就原先是字符串，现在把字符串换成数组超级大水题

代码：

#include<stdio.h>
#include<bits/stdc++.h> 
using namespace std;
int s[1000100],t[11000];
int nex[1000100];//nex数组大小和短串一致
int ans,n,m;
inline void get_nex()
{
    int j=-1;//影响next[0] 
    for (int i=0;i<m;i++){
        while(t[i]!=t[j+1] && j!=-1)
			j=nex[j];
        if (t[i]==t[j+1] && i!=0) 
			j++;
        nex[i]=j;
	}
}
inline void kmp()
{
    int j=-1;
    for (int i=0;i<n;i++){
        while(s[i]!=t[j+1] && j!=-1) 
			j=nex[j];
        if (s[i]==t[j+1]) j++;
        if (j==m-1){
        	ans++;
			printf("%d\n",i-j+1);
			break; 
		}
    }
}
int main()
{
	int tt;
	scanf("%d",&tt);
	while(tt--){
		ans=0;
		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]);
		get_nex();
		kmp();
		if(ans==0)printf("-1\n");
	}
}