Ladies_Man

KnuttMorrisPratt поиск вхождений подстроки в строку

Dec 17th, 2013
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.31 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int *pi;
  6.  
  7. void prefix(char *str, int ind)
  8. {
  9.     int i, t = 0;
  10.     pi[0] = 0;
  11.  
  12.         for (i = ind; i < strlen(str); i++) {
  13.         //t = pi[t - 1];
  14.     while ((t > 0) && (str[t] != str[i]))
  15.             t = pi[t - 1];
  16.         if (str[t] == str[i])
  17.                 t++;
  18.     pi[i] = t;
  19.     }
  20. }
  21.  
  22. void res (char *str, char *str_2, int ind)
  23. {
  24.     int i, t = 0, k = strlen(str);
  25.  
  26.     for (i = ind; i < strlen(str_2); i++) {
  27.         //t = pi[t - 1];
  28.         while ((t > 0) && (str[t] != str_2[i]))
  29.             t = pi[t - 1];
  30.         if (str[t] == str_2[i])
  31.                 t++;
  32.         if (t == k) {
  33.                 if (i - k + 1 >= 0) {
  34.                       printf("%d ", i - k + 1);
  35.                 }
  36.         }
  37.  
  38.     }
  39.     printf("\n");
  40. }
  41.  
  42. void kmpsubst(char *s, char *t)
  43. {
  44.     int i = 1, l, real_index;
  45.  
  46.     //printf("%s\n%s\n", s, t);
  47.     char *s_res;
  48.  
  49.     l = strlen(s) + strlen(t) + 1;
  50.     pi = (int*)malloc(l * sizeof(int));
  51.     //s_res = (char*)malloc((l + 1) * sizeof(char));
  52.  
  53.     prefix (s, i);
  54.         res (s, t, i-1);
  55.  
  56.         free(pi);
  57.     //free(s_res);
  58. }
  59.  
  60. int main(int argc, char **argv)
  61. {
  62.     //char a[100];
  63.     //scanf("%s", a);
  64.    // char b[100];
  65.     //scanf("%s", b);
  66.     kmpsubst(argv[1], argv[2]);
  67.     //kmpsubst (a, b);
  68.  
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment