Advertisement
awsmpshk

z-function

Oct 6th, 2021
876
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. std::vector<int> effectiveZFunction(std::string s) {
  2.     int n = (int)(s.length());
  3.     int left = 0, right = 0;
  4.     std::vector<int> zf(n);
  5.     for (int i = 0; i < n; ++i) {
  6.         zf[i] = std::max(0, std::min(right - i, zf[i - left]));
  7.         while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]]) zf[i]++;
  8.         if (i + zf[i] > right) {
  9.             left = i;
  10.             right = i + zf[i];
  11.         }
  12.     }
  13.  
  14.     return zf;
  15. }
Advertisement
RAW Paste Data Copied
Advertisement