XiaoYang有一個一點也不通用的寄存器。之所以說它不通用，是因為它真的很長！

XiaoYang有兩串數字，分別為 a1, a2, …, aN?和 b1, b2, …, bM。
今天，Victoryztk問XiaoYang，是否能找到數字 K，使得 aK?= b1, aK+1?= b2, …, aK+M-1?= bM？
XiaoYang立刻想起了他的不通用寄存器。可等到XiaoYang找到電路板時，發現它也被gclx搞壞了！

嚶嚶嚶，這可怎么辦啊。快來幫幫XiaoYang吧！

Input

輸入的第一行是測試組數 T。
每個測試樣例包含三行輸入，第一行是 N (1 ≤ N ≤ 106), M(1 ≤ M ≤ 104)，第二行是 a1, a2, …, aN，第三行是 b1, b2, …, bM。保證所有數字在 [-1000000, 1000000] 范圍內。

Output

對于每一個測試點，你應該輸出一行，其中包含K。如果有很多個K，輸出最小的一個。如果沒有K，輸出-1。

Sample Input

2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1

Sample Output

6 -1

#include<stdio.h>
#include<iostream>
using namespace std;
int a[10000005],b[10005];
int nxt[10005];
void getnxt(int m)
{
?? ?int k=-1,i=0;
?? ?nxt[0]=-1;
?? ?while(i<m)
?? ?{
?? ??? ?if(k==-1||b[i]==b[k])
?? ??? ?{
?? ??? ??? ?nxt[++i]=++k;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?k=nxt[k];
?? ??? ?}
?? ?}
}
int kmp(int n,int m){
?? ?int i=0,k=0;
?? ?while(i<n&&k<m){
?? ??? ?if(a[i]==b[k]||k==-1){
?? ??? ??? ?i++; k++;
?? ??? ?} ?
?? ??? ?else k=nxt[k];
?? ?}
?? ?if(k==m) return i-k+1;?
?? ?return -1;
}
int main()
{
?? ?int T,n,m,i,j;
?? ?scanf("%d",&T);
?? ?while(T--)
?? ?{
?? ? scanf("%d%d",&n,&m);
?? ? for(i=0;i<n;++i)
?? ? scanf("%d",&a[i]);
?? ? for(j=0;j<m;++j)
?? ? scanf("%d",&b[j]);
?? ? getnxt(m);
?? ? cout<<kmp(n,m)<<endl;
?? ?}
}

rxx很皮 ，喜歡偷偷刪掉cry的部分代碼，但rxx有強迫癥，只會刪掉相同的部分。

cry的代碼都是用可見ASCII字符表示。cry的代碼和rxx刪掉的部分不會超過1000個字符長。如果遇見#字符，rxx就結束刪代碼的工作。

請問rxx最多能刪掉cry多少處代碼。

Input

輸入包含多組數據，遇到#字符則表明輸入結束。
每組數據只有一行，包含cry的代碼和rxx要刪掉的部分，用空格隔開。

Output

輸出rxx最多能刪掉多少處代碼，如果一處都刪不掉，rxx只能灰溜溜的輸出0，每個結果占一行。

Sample Input

crycrycry cry
lalalalal lal
tpt tptptpt
wannacry? naive
#

Sample Output

3
2
0
0

?

#include<cstdio>
#include<cstring>
using namespace std;
char a[1005];
char b[1005];
int lena,lenb;
int nxt[1005];
void getnext()
{
? ? int i=0,k=-1;
? ? nxt[0]=-1;
? ? while(i<lenb)
? ? {
? ? ? ? if(k==-1||b[i]==b[k])
? ? ? ? {
? ? ? ? ? ? i++;
? ? ? ? ? ? k++;
? ? ? ? ? ? nxt[i]=k;
? ? ? ? }
? ? ? ? else ? ?k=nxt[k];
? ? }
}
int KMP()
{
? ? getnext();
? ? int i=0,k=0;
? ? int sum=0;
? ? while(i<lena&&k<lenb)
? ? {
? ? ? ? if(k==-1||a[i]==b[k])
? ? ? ? {
? ? ? ? ? ? i++;
? ? ? ? ? ? k++;
? ? ? ? }
? ? ? ? else ? ?k=nxt[k];
? ? ? ? if(k==lenb)
? ? ? ? {
? ? ? ? ? ? sum++;
? ? ? ? ? ? k=0;
? ? ? ? }
? ? }
? ? return sum;
}
int main()
{
? ? while(scanf("%s",a)!=EOF)
? ? {
? ? ? ? if(*a=='#'&&a[1]=='\0') ? ?break;
? ? ? ? scanf("%s",b);
? ? ? ? lena=strlen(a);
? ? ? ? lenb=strlen(b); ? ?
? ? ? ? printf("%d\n",KMP());
? ? }
? ?
? ? return 0;
}

總結

以上是生活随笔為你收集整理的KMP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。