string/manacher.cpp

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

Code

vector<int> manacher(const string &s){
    vector<int> res(s.size());
    int i = 0, j = 0;
    while(i < s.size()){
        while(i >= j && i + j < s.size() && s[i-j] == s[i+j]) ++j;
        res[i] = j;
        int k = 1;
        while(i >= k && i + k < s.size() && k + res[i-k] < j) res[i+k] = res[i-k], ++k;
        i += k; j -= k;
    }
    return res;
}

#line 1 "string/manacher.cpp"
vector<int> manacher(const string &s){
    vector<int> res(s.size());
    int i = 0, j = 0;
    while(i < s.size()){
        while(i >= j && i + j < s.size() && s[i-j] == s[i+j]) ++j;
        res[i] = j;
        int k = 1;
        while(i >= k && i + k < s.size() && k + res[i-k] < j) res[i+k] = res[i-k], ++k;
        i += k; j -= k;
    }
    return res;
}