qwq以下都为9.24后写的模板
#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;
}#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 160;
int n;
char s[M][N];
int trie[N][26], tot, endword[N], fail[N];
struct Node {
int num, pos;
} Ans[N];
inline void Init(int x) {
memset(trie[x], 0, sizeof(trie[x]));
fail[x] = endword[x] = 0;
}
inline void Build_Trie(int gg) {
int root = 0, len = strlen(s[gg] + 1);
for (int j = 1; j <= len; j++) {
if (!trie[root][s[gg][j] - 'a'])
trie[root][s[gg][j] - 'a'] = ++tot, Init(tot);
root = trie[root][s[gg][j] - 'a'];
}
endword[root] = gg;
}
inline void Get_Fail() {
queue <int> q;
for (int i = 0; i < 26; i++)
if (trie[0][i]) {
q.push(trie[0][i]);
fail[trie[0][i]] = 0;
}
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (trie[now][i]) {
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);
}
else {
trie[now][i] = trie[fail[now]][i];
}
}
}
inline int query() {
int len = strlen(s[n + 1] + 1), ans = 0, now = 0;
for (int i = 1; i <= len; i++) {
now = trie[now][s[n + 1][i] - 'a'];
for (int j = now; j; j = fail[j])
Ans[endword[j]].num++;
}
return ans;
}
inline bool cmp(Node x, Node y) {
return x.num > y.num || (x.num == y.num && x.pos < y.pos);
}
int main() {
scanf("%d", &n);
while (n != 0) {
tot = 0;
Init(0);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
Ans[i].num = 0, Ans[i].pos = i;
Build_Trie(i);
}
fail[0] = 0;
Get_Fail();
scanf("%s", s[n + 1] + 1);
query();
std::sort(Ans + 1, Ans + 1 + n, cmp);
printf("%d\n%s\n", Ans[1].num, s[Ans[1].pos] + 1);
for (int i = 2; i <= n; i++)
if (Ans[1].num == Ans[i].num)
printf("%s\n", s[Ans[i].pos] + 1);
else
break;
scanf("%d", &n);
}
return 0;
}（静态区间第k小）
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int l[N << 5], r[N << 5], cnt, sum[N << 5], a[N], b[N], c[N], n, q, m;
inline int read() {
int x = 0, k = 1; char c = getchar();
for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');
for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);
return k ? x : -x;
}
inline int Build(int t, int w) {
int now = ++cnt, mid = (t + w) >> 1;
sum[now] = 0;
if (t < w) {
l[now] = Build(t, mid);
r[now] = Build(mid + 1, w);
}
return now;
}
inline int add(int k, int t, int w, int x) {
int now = ++cnt, mid = (t + w) >> 1;
l[now] = l[k], r[now] = r[k], sum[now] = sum[k] + 1;
if (t < w && x <= mid)
l[now] = add(l[k], t, mid, x);
else if (t < w && x > mid)
r[now] = add(r[k], mid + 1, w, x);
return now;
}
inline int ask(int L, int R, int t, int w, int x) {
if (t >= w)
return t;
int mid = (t + w) >> 1, k = sum[l[R]] - sum[l[L]];
if (k >= x)
return ask(l[L], l[R], t, mid, x);
else
return ask(r[L], r[R], mid + 1, w, x - k);
}
int main() {
n = read(), q = read();
for (int i = 1; i <= n; i++)
b[i] = a[i] = read();
std::sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
c[0] = Build(1, m);
for (int i = 1; i <= n; i++) {
int now = lower_bound(b + 1, b + 1 + m, a[i]) - b;
c[i] = add(c[i - 1], 1, m, now);
}
for (int i = 1; i <= q; i++) {
int x = read(), y = read(), z = read();
printf("%d\n", b[ask(c[x - 1], c[y], 1, m, z)]);
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N = 31000000;
int len, hw[N], ans;
char s[N];
inline void Manacher() {
int maxright = 0, mid = 0;
for (int i = 1; i < len; i++) {
if (i < maxright)
hw[i] = std::min(hw[(mid << 1) - i], hw[mid] + mid - i);
else
hw[i] = 1;
while (s[i + hw[i]] == s[i - hw[i]])
++hw[i];
if (hw[i] + i > maxright)
maxright = hw[i] + i, mid = i;
}
}
int main() {
scanf("%s", s + 1);
len = strlen(s + 1);
for (int i = len; i >= 1; i--)
s[i * 2] = s[i];
s[0] = s[1] = '#';
for (int i = 1; i <= len; i++)
s[i * 2 + 1] = '#';
s[len * 2 + 2] = 0;
len = len * 2 + 2;
Manacher();
ans = 1;
for (int i = 0; i < len; i++)
ans = std::max(ans, hw[i]);
printf("%d\n", ans - 1);
return 0;
}原文：https://www.cnblogs.com/wjnclln/p/11585442.html