Advertisement
awsmpshk

Z-function

Sep 28th, 2021
717
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Naive realization
  2.  
  3. std::vector<int> zFunction(std::string s) {
  4.     int n = (int)(s.length());
  5.     std::vector<int> zf(n);
  6.     zf[0] = 0;
  7.     for (int i = 0; i < n; ++i) {
  8.         while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]]) zf[i]++;
  9.     }
  10.    
  11.     return zf;
  12. }
  13.  
  14. // Effective realization
  15.  
  16. std::vector<int> effectiveZFunction(std::string s) {
  17.     int n = (int)(s.length());
  18.     int left = 0, right = 0;
  19.     std::vector<int> zf(n);
  20.     for (int i = 0; i < n; ++i) {
  21.         zf[i] = max(0, min(right - i, zf[i - left]));
  22.         while (zf[i] < n && s[zf[i]] == s[i + zf[i]]) zf[i]++;
  23.         if (i + zf[i] > right) {
  24.             left = i;
  25.             right = i + zf[i];
  26.         }
  27.     }
  28.    
  29.     return zf;
  30. }
Advertisement
RAW Paste Data Copied
Advertisement