string/z-algorithm.cpp

• View this file on GitHub
• Last update: 2020-04-26 17:42:59+09:00

Code

vector<int> Z_algorithm(const string &s){
    vector<int> res(s.size());
    res.front() = s.size();
    for (int i = 1, j = 0; i < s.size(); ++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 < s.size() && s[k] == s[i+k]) ++k;
            res[i] = k;
            j = i;
        }
    }
    return res;
}

#line 1 "string/z-algorithm.cpp"
vector<int> Z_algorithm(const string &s){
    vector<int> res(s.size());
    res.front() = s.size();
    for (int i = 1, j = 0; i < s.size(); ++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 < s.size() && s[k] == s[i+k]) ++k;
            res[i] = k;
            j = i;
        }
    }
    return res;
}

Back to top page