string/z-algorithm.hpp

View this file on GitHub
Last update: 2024-06-15 00:08:38+07:00
Include: #include "string/z-algorithm.hpp"

Verified with

verify/yosupo/string/zalgorithm.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Z Algorithm. z[i] := the length of the longest common prefix between s and s[i:].
 */

template<class STR>
vector<int> z_algorithm(const STR &s){
    int n=(int)s.size();
    vector<int> z(n);
    z[0]=n;
    for(int i=1,l=0,r=1;i<n;i++){
        if(i<r)z[i]=min(r-i,z[i-l]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]>r)l=i,r=i+z[i];
    }
    return z;
}

#line 2 "string/z-algorithm.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Z Algorithm. z[i] := the length of the longest common prefix between s and s[i:].
 */

template<class STR>
vector<int> z_algorithm(const STR &s){
    int n=(int)s.size();
    vector<int> z(n);
    z[0]=n;
    for(int i=1,l=0,r=1;i<n;i++){
        if(i<r)z[i]=min(r-i,z[i-l]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]>r)l=i,r=i+z[i];
    }
    return z;
}