Ciemny_Cygan

KMP

Oct 18th, 2020 (edited)
371
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. void preKMP(string pattern, int f[]) {
  7.     int m = pattern.length(), k;
  8.     f[0] = -1;
  9.  
  10.     for (int i = 1; i < m; i++) {
  11.         k = f[i - 1];
  12.         while (k >= 0) { if (pattern[k] == pattern[i - 1]) break; else k = f[k]; }
  13.         f[i] = k + 1;
  14.     }
  15. }
  16.  
  17. int KMP(string pattern, string target) {
  18.     int i = 0, k = 0, m = pattern.length(), n = target.length();
  19.     int f[m];    
  20.  
  21.     preKMP(pattern, f);    
  22.  
  23.     while (i < n) {
  24.         if (k == -1) {
  25.             i++;
  26.             k = 0;
  27.         } else if (target[i] == pattern[k]) {
  28.             i++;
  29.             k++;
  30.  
  31.             if (k == m) return i - k;
  32.         } else k = f[k];
  33.     }
  34.     return -1;
  35. }
  36.  
  37. int main() {
  38.     string tar, pat;
  39.     int n = 0, p = 0;
  40.        
  41.     getline(cin, tar);
  42.     getline(cin, pat);
  43.  
  44.     while (n < tar.length())
  45.     {
  46.         if (KMP(pat, tar) != -1) {
  47.             cout << KMP(pat, tar) + p << endl;
  48.             p += KMP(pat, tar) + 1;
  49.             tar = tar.substr(KMP(pat, tar) + 1);
  50.         }
  51.         n++;
  52.     }
  53.     return 0;
  54. }
RAW Paste Data