欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[模板]PAM

程序员文章站 2022-03-12 08:01:57
...

模板\([luogu5496]\)

题目

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
char s[N];
int Len;
struct PAM{
    int last, cnt, len[N], fail[N], num[N], k, p, ch[N][26], p1, c[N];
    //char s[N];
    void init(char *s) {
        last = 0, cnt = 1, len[0] = 0, len[1] = -1, fail[0] = 1, fail[1] = 0, s[0] = 26;
    }
    void insert() {
        for (int i = 1; i <= Len; i++) {
            s[i] = (s[i] - 97 + k) % 26 + 97;
            c[i] = s[i] - 'a';
            p = last;
            while (s[i - len[p] - 1] != s[i])
                p = fail[p];
            if (!ch[p][s[i]]) {
                len[++cnt] = len[p] + 2, p1 = fail[p];
                while (s[i - len[p1] - 1] != s[i])
                    p1 = fail[p1];
                fail[cnt] = ch[p1][s[i]];
                num[cnt] = num[fail[cnt]] + 1;
                ch[p][s[i]] = cnt;
            }
            last = ch[p][s[i]];
            printf("%d%c", num[last], (i == Len) ? '\n' : ' ');
            k = num[last];
            }
    }
} s1;
int main() {
    scanf("%s", s + 1);
    Len = strlen(s + 1);
    s1.init(s);
    s1.insert();
    return 0;
}