[模板]PAM

模板\([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;

}
巴特西

[模板]PAM

最新文章

热门文章
