【题解】【NOIp2020 T2 P7114 字符串匹配】

· · 题解

首先考虑暴力：令 T=AB，从小到大枚举 T 的长度，找到最短的 C_1，枚举有多少个 T 的真前缀 A 满足 F(A) \leqslant F(C_1)，之后令 C_2=ABC，再令 C_3=ABABC……以此类推

然后我们发现 F(S) 比较诡异特殊，考虑从它来优化。结合上面的暴力分析，容易想到 F(C_k) 的前面的所有 ABAB 均不会对其产生贡献，故有 F(C_{2n-1})=F(C_1)，F(C_{2n})=F(C_2)

所以，A,B,C 是一组解就意味着 A,B,ABABC 也是一组解（如果 AB 的重复次数 \geqslant 3），那么我们无需枚举所有的 C_k，而只需计算 C_1 与 C_2 解的数量，再分别乘上有多少 C_k 与其相同即可

最后我们发现时间复杂度的瓶颈在于找到最短的 C，看出这个问题本质是求 T 的最大重复次数，使用字符串 Hash 即可

此算法是 n (\ln n+\log_2 26) 的

具体实现还有一（很）些（多）细节，参见代码

#include <cstdio>
#include <cstring>
#include <cctype>
typedef unsigned long long ULL;
const ULL MAXN = (1 << 20) + 5, BASE = 2017;
char s[MAXN]; // 读入的字符串 
int t, len; // t为数据组数，len为字符串长度 
ULL h[MAXN]; // h[i]表示   长度为i的前缀 的Hash值 
int jcnt, djcnt[MAXN]; // jcnt表示F(T)，djcnt[i]表示 F(S_i至S_n组成的字符串) 
bool isj[30], disj[30]; // （i从0开始）isj[i]表示第i个字母出现奇数次是true/false，disj[i]意义与isj[i]相同，但为倒序更新 
ULL ans; // 答案 
//int cnt[30]; // cnt[i]表示有i个字母出现奇数次的T的真前缀的数量 
int bit[30]; // 表示由cnt[i]构成的树状数组 

inline int lowbit(int x)
{ return x & (-x); }

void update(int x) {
    ++x; //树状数组不能处理下标为0的情况，故“平移”一位 
    while(x <= 27) {
        ++bit[x];
        x += lowbit(x);
    }
}

int sum(int x) {
    ++x;
    int s = 0;
    while(x >= 1) {
        s += bit[x];
        x -= lowbit(x);
    }
    return s;
}
// 手写读入，返回读入字符串的长度
// （但好像并没有什么卵用 
int input(char* s) {
    char c = getchar();
    int i = 0;
    while(!islower(c))
        c = getchar();
    while(islower(c)) {
        s[++i] = c;
        c = getchar();
    }
    return i;
}

int main() {
//  freopen("string.in", "r", stdin);
//  freopen("string.out", "w", stdout);
    scanf("%d", &t);
    while(t--) {
        len = input(s);
        djcnt[len] = 1; // 最后一个字符重复了一次（奇数次） 
        disj[s[len] - 'a'] = 1; // 最后一个字符出现奇数次=true 
        for(int i = len - 1; i >= 1; --i) //预处理djcnt[i]以快速计算C 
            djcnt[i] = djcnt[i + 1] + ((disj[s[i] - 'a'] = !disj[s[i] - 'a']) == 1 ? 1 : -1);
        h[1] = s[1] - 'a'; // 第1个字符的Hash值 
        for(int i = 2; i <= len; ++i) // 递推计算Hash值 
            h[i] = h[i - 1]*BASE + s[i] - 'a';
        ULL a = BASE*BASE;
        update(1); // 第一个字符重复了一次（奇数次） 
        isj[s[1] - 'a'] = 1; // 第一个字符出现奇数次=true 
        jcnt = 1; // 有一个字符出现奇数次 
        for(int i = 2; i < len; ++i) { // 循环从2开始（否则A,B中必有一空串）到len-1结束（否则C为空串） 
            int x = 1; // T的循环次数 
            for(int j = (i << 1); j <= len; j += i) {
                /* e.g.
                 * h[i]: abc
                 * h[j - i]:          abcabc
                 * h[j]:              abcabc???
                 * h[j - i]*a:        ---abcabc
                 * h[j] - h[j - i]*a: abc
                 * 容易发现只有???=abc才有h[j] - h[j - i]*a == h[i] 
                 */
                if(h[j] - h[j - i]*a == h[i])
                    ++x;
                else
                    break;
            }
            // 后面四行是计算A,B,C的情况 
            if(x*i == len) //此时x*i+1=len+1，由于我没有清空djcnt所以不能把djcnt[len+1]视为0，故不能沿用else情况的代码 
                ans += 1ULL*bit[1]*((x - 1) >> 1); // C不能是空串，故比else的情况少一个C 
            else
                ans += 1ULL*sum(djcnt[x*i + 1])*((x + 1) >> 1); // C_1,C_3,...,C_k（k为奇数且<=x）都可以 
            // 后面一行是计算A,B,ABC的情况 
            ans += 1ULL*sum(djcnt[(x - 1)*i + 1])*(x >> 1); // C_2,C_4,...,C_k（k为奇数且<=x）都可以 
            update((isj[s[i] - 'a'] = !isj[s[i] - 'a']) ? ++jcnt : --jcnt); // 注意这里要在计算后更新，否则B可能会为空串 
            a *= BASE; //T的长度增加，a也要随之增加 
        }
        printf("%llu\n", ans);
        memset(disj, 0, sizeof(disj));
        memset(isj, 0, sizeof(isj));
        memset(bit, 0, sizeof(bit));
        ans = 0;
    }
    return 0;
}