Advertisement
palmerstone

kmp

Nov 1st, 2012
3,173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. int t, line, n, m, ar[1000100], ar2[10010], P[10010];
  4.  
  5. void prefix_function(){
  6.     int i, k = -1;
  7.     P[0] = k;
  8.  
  9.     for (i = 1; i < m; i++){
  10.         while (k > -1 && (ar2[k + 1] != ar2[i])) k = P[k];
  11.         if (ar2[i] == ar2[k + 1]) k++;
  12.         P[i] = k;
  13.     }
  14. }
  15.  
  16. int kmp(){
  17.     int i, k = -1;
  18.     for (i = 0; i < n; i++){
  19.         while (k > -1 && ar2[k + 1] != ar[i]) k = P[k];
  20.         if (ar[i] == ar2[k + 1]) k++;
  21.  
  22.         if (k == (m - 1)){
  23.             return (i - k + 1);
  24.         }
  25.     }
  26.     return (-1);
  27. }
  28.  
  29. int main(){
  30.     int i, j;
  31.     scanf("%d", &t);
  32.  
  33.     for (line = 1; line <= t; line++){
  34.         scanf("%d %d", &n, &m);
  35.         for (i = 0; i < n; i++) scanf("%d", &ar[i]);
  36.         for (i = 0; i < m; i++) scanf("%d", &ar2[i]);
  37.         prefix_function();
  38.         int res = kmp();
  39.         printf("%d\n", res);
  40.     }
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement