一道板子题

Description

求给定字符串中回文串的个数

题意够显然了，懒得放样例了

来复习复习马拉车.

马拉车就是通过回文的性质优化了时间复杂度．

先在字符间插入一个不会出现的字符（通常使用’#’），使得字符串长度为奇数，然后搞一搞就出来了．

等有时间了回家好好写!

#include <cstdio>
#include <cstring>
#define min(x,y) x > y ? x = y : 0
#define RI register int

const int N = 1000002;
int n, maxid, id, ans, p[N << 1];
char c[N];

int main() {
    scanf("%s", c), n = strlen(c);
    for (RI i = n - 1; i >= 0; --i) c[(i << 1) + 2] = c[i], c[(i << 1) + 3] = '#';
    n = (n << 1) + 2, c[0] = c[1] = '#';
    for (RI i = 1; i < n; ++i) {
        if (i < maxid) p[i] = min(p[(id << 1) - i], p[id] + id - i);
        else p[i] = 1;
        while (c[i + p[i]] == c[i - p[i]]) ++p[i];
        if (p[i] + i> maxid) maxid = p[i] + i, id = i;
        ans += (p[i] >> 1);
    }
    printf("%d", ans);
}

哦完结了！