Fshl0

KMP

Mar 9th, 2020
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. string a, b;
  2. cin >> a >> b;
  3. string s = b;
  4. s += '#'; s += a;
  5. lps[0] = 0;
  6. for (int i = 1; i < s.length(); i++) {
  7.     int len = lps[i - 1];
  8.     while (len > 0 && s[len] != s[i])
  9.          len = lps[len - 1];
  10.     if (s[i] == s[len])
  11.          len++;
  12.     lps[i] = len;
  13.     if (lps[i] == b.size())
  14.         v.pb(i);
  15. }
RAW Paste Data