首先很容易观察到 $b$ 的长度越长越好，因为 $b$ 长度 $+1$，两边至多 $-1$。
然后注意 $a’$ 是一段后缀，因此可以枚举 $b$ 的对称中心，然后 Manacher 求出 $[l,r]$ 回文串。
可以预处理出 $[1,i]$ 的最长子串满足它可以和 $S$ 的一段后缀翻转匹配。

讲个笑话我直接暴力扩展，这显然是错的，因为如果从当前节点重新开始可能之前还有一段可以匹配。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
char s[N];

int f[N];
void Manacher() {
    int l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = (i >= r) ? 1 : min(f[l + r - i], r - i + 1);
        while (i - f[i] >= 1 && i + f[i] <= n && s[i - f[i]] == s[i + f[i]]) f[i]++;
        if (i + f[i] > r) l = i - f[i] + 1, r = i + f[i] - 1;
    }
}

int len[N], pos[N]; // [1,i] 能匹配的最长后缀长度以及结尾位置
void init() {
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == s[n - now] && i < n - now) len[i] = ++now, pos[i] = i;
        else len[i] = now = 0, pos[i] = i;
        if (len[i - 1] > len[i]) len[i] = len[i - 1], pos[i] = pos[i - 1];
    }
}

int getval(int i) {
    int l = i - f[i] + 1, r = i + f[i] - 1;
    int ll = min(len[l - 1], n - r);    //能匹配的最长长度
    return ll + ll + f[i] * 2 - 1;
}

void print(int i) {
    int l = i - f[i] + 1, r = i + f[i] - 1;
    int ll = min(len[l - 1], n - r);    //能匹配的最长长度
    if (!ll) {
        puts("1");
        printf("%d %d\n", l, f[i] * 2 - 1);
    } else {
        puts("3");
        printf("%d %d\n", pos[l - 1] - ll + 1, ll);
        printf("%d %d\n", l, f[i] * 2 - 1);
        printf("%d %d\n", n - ll + 1, ll);
    }
}

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    Manacher(), init();
    int Max = 0, id = 0;
    for (int i = 1; i <= n; i++)
        if (Max < getval(i)) Max = getval(i), id = i;
    print(id);
    return 0;
}

正确做法是 KMP 匹配后缀。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
char s[N], t[N];

int f[N];
void Manacher() {
    int l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = (i >= r) ? 1 : min(f[l + r - i], r - i + 1);
        while (i - f[i] >= 1 && i + f[i] <= n && s[i - f[i]] == s[i + f[i]]) f[i]++;
        if (i + f[i] > r) l = i - f[i] + 1, r = i + f[i] - 1;
    }
}

int len[N], pos[N]; // [1,i] 能匹配的最长后缀长度以及结尾位置
int nxt[N];
void init() {
    for (int i = n; i >= 1; i--) t[i] = s[n - i + 1];
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && t[i] != t[j + 1]) j = nxt[j];
        if (t[i] == t[j + 1]) j++;
        nxt[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != t[j + 1]) j = nxt[j];
        if (s[i] == t[j + 1]) j++;
        len[i] = j, pos[i] = i;
        if (j == n) j = nxt[j];
    }
    for (int i = 1; i <= n; i++)
        if (len[i - 1] > len[i]) len[i] = len[i - 1], pos[i] = pos[i - 1];
}

int getval(int i) {
    int l = i - f[i] + 1, r = i + f[i] - 1;
    int ll = min(len[l - 1], n - r);    //能匹配的最长长度
    return ll * 2 + f[i] * 2 - 1;
}

void print(int i) {
    int l = i - f[i] + 1, r = i + f[i] - 1;
    int ll = min(len[l - 1], n - r);    //能匹配的最长长度
    if (!ll) {
        puts("1");
        printf("%d %d\n", l, f[i] * 2 - 1);
    } else {
        puts("3");
        printf("%d %d\n", pos[l - 1] - ll + 1, ll);
        printf("%d %d\n", l, f[i] * 2 - 1);
        printf("%d %d\n", n - ll + 1, ll);
    }
}

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    Manacher(), init();
    int Max = 0, id = 0;
    for (int i = 1; i <= n; i++)
        if (Max < getval(i)) Max = getval(i), id = i;
    print(id);
    return 0;
}