Number Sequence

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 15683 Accepted Submission(s): 6898

Problem Description

Given 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.

Input

The 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].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

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 

初学KMP，水一发模版题

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
              10 #include 
              
               11 #include 
               
                12 13 using namespace std;14 const int maxn = 1000010;15 int na, nb;16 int a[maxn];17 int b[maxn];18 int pre[maxn];19 20 void getpre(int *b, int *pre) {21 int j, k;22 pre[0] = -1;23 j = 0;24 k = -1;25 while(j < nb - 1) {26 if(k == -1 || b[j] == b[k]) { //匹配27 j++;28 k++;29 pre[j] = k;30 }31 else { //b[j] != b[k]32 k = pre[k];33 }34 }35 }36 37 int kmp() {38 int i = 0;39 int j = 0;40 getpre(b, pre);41 while(i < na) {42 if(j == -1 || a[i] == b[j]) {43 i++;44 j++;45 }46 else {47 j = pre[j];48 }49 if(j == nb) {50 return i - nb + 1;51 }52 }53 return -1;54 }55 56 int main() {57 int T;58 scanf("%d", &T);59 while(T--) {60 scanf("%d %d", &na, &nb);61 for(int i = 0; i < na; i++) {62 scanf("%d", &a[i]);63 }64 for(int i = 0; i < nb; i++) {65 scanf("%d", &b[i]);66 }67 printf("%d\n", kmp());68 }69 return 0;70 }

本题还可以用hash做，效率与kmp差距不大。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 14 using namespace std;15 16 typedef unsigned long long ull;17 const int B = 100007;18 const int maxn = 1000010;19 int a[maxn], b[maxn];20 int na, nb;21 22 ull quickmul(int x, int n) {23 ull ans = 1;24 ull t = x;25 while(n) {26 if(n & 1) {27 ans = (ans * t);28 }29 t = t * t;30 n >>= 1;31 }32 return ans;33 }34 35 int contain() {36 if(na > nb) {37 return false;38 }39 ull t = quickmul(B, na);40 ull ah = 0, bh = 0;41 for(int i = 0; i < na; i++) {42 ah = ah * B + a[i];43 }44 for(int i = 0; i < na; i++) {45 bh = bh * B + b[i];46 }47 for(int i = 0; i + na <= nb; i++) {48 if(ah == bh) {49 return i + 1;50 }51 if(i + na < nb) {52 bh = bh * B + b[i+na] - b[i] * t;53 }54 }55 return -1;56 }57 int main() {58 // freopen("in", "r", stdin);59 int T;60 scanf("%d", &T);61 while(T--) {62 scanf("%d %d", &nb, &na);63 for(int i = 0; i < nb; i++) {64 scanf("%d", &b[i]);65 }66 for(int i = 0; i < na; i++) {67 scanf("%d", &a[i]);68 }69 printf("%d\n", contain());70 }71 return 0;72 }

转载于:https://www.cnblogs.com/kirai/p/4754521.html

你可能感兴趣的文章