Number Sequence - HDU 1711(KMP模板题)

时间:2023-03-08 16:43:23

题意:给你一个a串和一个b串,问b串是否是a串的子串,如果是返回b在a中最早出现的位置,否则输出-1

分析:应该是最简单的模板题了吧.....
代码如下:
==============================================================================================
#include<stdio.h>
#include<string.h> const int MAXM = 1e4+;
const int MAXN = 1e6+; int a[MAXN], b[MAXM], next_b[MAXM]; void GetNext(int b[], int next[], int M)
{
int i=, j=-;
next[] = -; while(i < M)
{
if(j==- || b[i]==b[j])
next[++i] = ++j;
else
j = next[j];
}
}
int KMP(int a[], int b[], int next[], int N, int M)
{
int i = , j = ; while(i < N)
{
while(j==- || a[i] == b[j] && j<M)
i++, j++; if(j == M)return i-M+; j = next[j];
} return -;
} int main()
{
int T; scanf("%d", &T); while(T--)
{
int i, N, M; scanf("%d%d", &N, &M); for(i=; i<N; i++)
scanf("%d", &a[i]);
for(i=; i<M; i++)
scanf("%d", &b[i]); GetNext(b, next_b, M); printf("%d\n", KMP(a, b, next_b, N, M));
} return ;
}