StoneHaos

11

Nov 30th, 2021
623
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. int KMP(string s, string p) {
  7.     int ans = -1;
  8.     int n = s.size();
  9.     int m = p.size();
  10.  
  11.     int *d = new int[m];
  12.     d[0] = 0;
  13.     int j = 0;
  14.     int i = 1;
  15.     while (i < m) {
  16.         while (j > 0 && p[j] != p[i])
  17.             j = d[j - 1];
  18.         if (p[j] == p[i])
  19.             j++;
  20.         d[i] = j;
  21.         i++;
  22.     }
  23.     j = 0;
  24.     i = 0;
  25.     while (i < n) {
  26.         while (j > 0 && p[j] != s[i])
  27.             j = d[j - 1];
  28.         if (p[j] == s[i])
  29.             j++;
  30.         if (j == m) {
  31.             ans = i - j + 1;
  32.             break;
  33.         }
  34.         i ++;
  35.     }
  36.     delete [] d;
  37.     return ans;
  38. }
  39.  
  40. int main() {
  41.     string s, p;
  42.     cin >> s >> p;
  43.     cout << KMP(s, p) << endl;
  44.     return 0;
  45. }
RAW Paste Data