Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- int t, line, n, m, ar[1000100], ar2[10010], P[10010];
- void prefix_function(){
- int i, k = -1;
- P[0] = k;
- for (i = 1; i < m; i++){
- while (k > -1 && (ar2[k + 1] != ar2[i])) k = P[k];
- if (ar2[i] == ar2[k + 1]) k++;
- P[i] = k;
- }
- }
- int kmp(){
- int i, k = -1;
- for (i = 0; i < n; i++){
- while (k > -1 && ar2[k + 1] != ar[i]) k = P[k];
- if (ar[i] == ar2[k + 1]) k++;
- if (k == (m - 1)){
- return (i - k + 1);
- }
- }
- return (-1);
- }
- int main(){
- int i, j;
- scanf("%d", &t);
- for (line = 1; line <= t; line++){
- scanf("%d %d", &n, &m);
- for (i = 0; i < n; i++) scanf("%d", &ar[i]);
- for (i = 0; i < m; i++) scanf("%d", &ar2[i]);
- prefix_function();
- int res = kmp();
- printf("%d\n", res);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement