string/prefix-function.hpp

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

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Prefix function. pi[i] := the length of the longest proper prefix of s[0:i] which is also a suffix of s[0:i].
 */

template<class STR>
vector<int> prefix_function(const STR &s){
    int n=(int)s.size();
    vector<int> pi(n);
    for(int i=1,j=0;i<n;i++){
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
    return pi;
}

#line 2 "string/prefix-function.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-14
 * Description: Prefix function. pi[i] := the length of the longest proper prefix of s[0:i] which is also a suffix of s[0:i].
 */

template<class STR>
vector<int> prefix_function(const STR &s){
    int n=(int)s.size();
    vector<int> pi(n);
    for(int i=1,j=0;i<n;i++){
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
    return pi;
}

Back to top page