思路与算法

计算字符串前缀函数pi，先对每个位置的pi值计数，再从长前缀往短前缀沿失配父链累加。最后每个前缀还要计入它自身开头的出现1次，仅对偶数长度累加总次数。

正确性说明

一个前缀在某个位置结束，当且仅当其长度在该位置的前缀失配链上。初始计最长边界，再沿失配链反向聚合，会把每个结束位置传播给全部相应短前缀。每个前缀自身位置的出现另外加1，故得到全部可重叠出现次数。筛选偶数长度恰好对应目标集合。

复杂度

前缀函数与反向聚合均O(n)，空间O(n)，pi及计数数组初始化O(n)已计入。n≤200000，答案可达10^10，必须用long long。独立答案使用Z函数后累加floor(Z[i]/2)，不同于失配链聚合。

易错点

允许出现重叠。不能把空前缀计入答案，也不能只数偶数下标的出现位置。长度为n的前缀也可能需要计入，开头自身的1次不要漏。两组公开样例均纳入评测。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1, j = 0; i < n; ++i) {
        while (j && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
    vector<long long> count(n + 1);
    for (int x : pi)
        ++count[x];
    for (int i = n; i > 0; --i)
        count[pi[i - 1]] += count[i];
    long long answer = 0;
    for (int i = 2; i <= n; i += 2)
        answer += count[i] + 1;
    cout << answer << '\n';
}