Z-Algorithm
(String/zalgo.hpp)

• View this file on GitHub
• Last update: 2023-01-17 03:26:22+09:00
• Include: #include "String/zalgo.hpp"

Verified with

• Verify/LC_zalgorithm.test.cpp

Code

#pragma once

template<typename T>vector<int> Zalgo(T& s){
   int n=s.size(); vector<int> res(n);
   for(int i=1,j=0;i<n;i++){
      if(i+res[i-j]<j+res[j])res[i]=res[i-j];
      else{
         int k=max(0,j+res[j]-i);
         while(i+k<n&&s[k]==s[i+k])k++;
         res[i]=k; j=i;
      }
   } res[0]=n; return res;
}

/**
 * @brief Z-Algorithm
 */

#line 2 "String/zalgo.hpp"

template<typename T>vector<int> Zalgo(T& s){
   int n=s.size(); vector<int> res(n);
   for(int i=1,j=0;i<n;i++){
      if(i+res[i-j]<j+res[j])res[i]=res[i-j];
      else{
         int k=max(0,j+res[j]-i);
         while(i+k<n&&s[k]==s[i+k])k++;
         res[i]=k; j=i;
      }
   } res[0]=n; return res;
}

/**
 * @brief Z-Algorithm
 */

Back to top page