Number Sequence
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15149 Accepted Submission(s): 6644Problem DescriptionGiven two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.InputThe first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].OutputFor each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.Sample Input213 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 1 313 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 2 1Sample Output6-1Source
题意:给两个串a,b;求b在a中首次出现的位置,若没有則输出-1;
1 #include<iostream> 2 #include<vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <math.h> 7 #include<algorithm> 8 #define ll long long 9 #define eps 1e-8 10 using namespace std; 11 12 int nexts[1000050]; 13 int str[1000050],b[10050]; 14 15 void pre_nexts(int m) 16 { 17 memset(nexts,0,sizeof(nexts)); 18 int j = 0,k = -1; 19 nexts[0] = -1; 20 while(j < m) 21 { 22 if(k == -1 || b[j] == b[k]) nexts[++j] = ++k; 23 else k = nexts[k]; 24 } 25 } 26 int KMP(int n,int m) 27 { 28 int i,j = 0; 29 for(i = 0; i < n; ) 30 { 31 if(str[i] == b[j]) 32 { 33 if(j == m-1) return i - (m - 1)+1;//匹配成功,返回起始坐标 34 i++,j++; 35 } 36 else 37 { 38 j = nexts[j]; 39 if(j == -1) { i++,j = 0;}//否则重新匹配 40 } 41 } 42 return -1; 43 } 44 int main(void) 45 { 46 int t,i,m,n; 47 scanf("%d",&t); 48 while(t--) 49 { 50 scanf("%d %d",&n,&m); 51 for(i = 0; i < n; i++) 52 scanf("%d",&str[i]); 53 for(i = 0; i < m; i++) 54 scanf("%d",&b[i]); 55 if(n < m) { printf("-1 "); continue;}//细节 56 pre_nexts(m); 57 printf("%d ",KMP(n,m)); 58 } 59 return 0; 60 }