F

Time Limit: 1000ms?? Memory limit: 65536K??有疑問？點這里^_^

題目描述

給出兩串數字A[ ]，B[ ]，如果B是A的子串，那么輸出B在A中第一次出現的位置，否則輸出-1。

輸入

第一行，輸入一個T，表明后面有幾組數據。每組數據的第一行，輸入兩個數N、M (1 <= N <= 1000000, 1 <= M <= 10000)，N表示第一行數字的個數，M表示第二行數字的個數。接下來兩行，分別輸入A數列和B數列。

輸出

輸出只有一行。如果數列B在數列A中出現過，輸出數列B在數列A中第一次出現的位置，如果沒有出現過，輸出-1。

示例輸入

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

示例輸出

6 10 -1 #include <stdio.h> #include <string.h> #include <stdlib.h> int next[10010]; int a[1000010],b[10010]; void get_next(int n)//next數組 {int i=0;int j=-1;next[0]=-1;while(i<n){if(j==-1||b[i]==b[j]){i++;j++;next[i]=j;}elsej=next[j];} } void KMP(int n1,int n2)//kmp算法 {int i=0;int j=0;while(i<n1&&j<n2){if(j==-1||a[i]==b[j]){i++;j++;}elsej=next[j];}if(j>=n2)printf("%d %d\n",i-j+1,i);//輸出輸出數列B在數列A中第一次出現的位置在數列A中的開始序號和終止序號elseputs("-1"); } int main() {int n,i,j,x,y;scanf("%d",&n);for(j=0;j<n;j++){scanf("%d %d",&x,&y);getchar();for(i=0;i<x;i++)scanf("%d",&a[i]);for(i=0;i<y;i++)scanf("%d",&b[i]);getchar();get_next(y);KMP(x,y);}return 0; }

轉載于:https://www.cnblogs.com/jiangyongy/p/3971669.html

總結

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

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