Ladies_Man

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

Dec 17th, 2013
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.07 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define max(x,y) ((x)>(y) ? (x):(y))
  5.  
  6. int fi1[1000] = {0}, fi2[1000] = {0}, sigma[500];
  7.  
  8. int *suffix (const char *str)
  9. {
  10.     int len = strlen(str), i = len - 2, t = i + 1;
  11.     sigma[t] = t;
  12.  
  13.     while (i >= 0) {
  14.         while ((t < len - 1) && (str[t] != str[i]))
  15.             t = sigma[t + 1];
  16.         if (str[t] == str[i]) t--;
  17.         sigma[i] = t;
  18.         i--;
  19.     }
  20.     return sigma;
  21. }
  22.  
  23. int *delta1 (const char *str)
  24. {
  25.     int i = 0, j = 0;
  26.  
  27.     while (i < 26) {
  28.         fi1[i] = strlen(str);
  29.         i++;
  30.     }
  31.     while (j < strlen(str)) {
  32.         fi1[str[j] - 61] = strlen(str) - j - 1;
  33.         j++;
  34.     }
  35.     return fi1;
  36. }
  37.  
  38. int *delta2 (const char *str)
  39. {
  40.     int *sigma = suffix(str);
  41.     int len = strlen(str), i = 0, j = 0, t = sigma[0];
  42.  
  43.     while (i < len) {
  44.         while (t < i) t = sigma[t + 1];
  45.         fi2[i] = len + t - i;
  46.         i++;
  47.     }
  48.     while (j < len - 1) {
  49.         t = j;
  50.         while (t < len - 1) {
  51.             t = sigma[t + 1];
  52.             if (str[j] != str[t]) fi2[t] = - (j + 1) + len;
  53.         //j++;
  54.         }
  55.         j++;
  56.     }
  57.     return fi2;
  58. }
  59.  
  60. int inc_k (const char *str_a, const char *str_b, int pos, int ind)
  61. {
  62.     int temp;
  63.     if (fi1[str_b[pos] - 61] > fi2[ind]) {
  64.         temp = pos + fi1[str_b[pos] - 61];
  65.         return temp;
  66.     }
  67.     if (fi1[str_b[pos] - 61] <= fi2[ind]) {
  68.         temp = pos + fi2[ind];
  69.         return temp;
  70.     }
  71.     else return strlen(str_b);
  72. }
  73.  
  74. int main (int argc, char **argv)
  75. {
  76.     //char s[100]; char t[100]; scanf("%s", s); scanf("%s", t);
  77.     char *s = argv[1];
  78.     char *t = argv[2];
  79.     int tlen = strlen(t), slen = strlen(s), k = slen - 1, i;
  80.     int *fi1 = delta1 (s);
  81.     int *fi2 = delta2 (s);
  82.  
  83.     while (k < tlen) {
  84.         i = slen - 1;
  85.         cycle:;
  86.         while (t[k] == s[i]) {
  87.             if (i == 0) {
  88.                 printf("%d ", k);
  89.                 break;
  90.             }
  91.             i--;
  92.             k--;
  93.         }
  94.         k = inc_k (s, t, k, i);
  95.     }
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment