题解 P3426 【[POI2005]SZA-Template】

· · 题解

一只国家集训队巨佬强制向我传了邪教(

然后我就邪教了......

就是...... 利用国家集训队级别的芝士切紫题

我们老师找我们做题, 我们去找大佬寻找思路, 然后大佬就翻出了一些......

......

下面进入正题

我们使用了什么特殊性质呢?

我们定义, 一个字符串s, 它的border是既是它的前缀又是它的后缀, 且不等于s本身的串.

然后我们定义真border是所有border中的最长者.

那么有这么一个神仙性质, 就是所有长度大于\lfloor|s|/2\rfloor的border的长度形成一个等差数列, 并且这些串可以互相表达.

然后我们又有一个神仙性质, 就是一个串的所有border长度是next[n], next[next[n]]...... 其中next就是KMP的数组......

是不是很神奇...... 证明比较复杂......

那么简单地证明一下......

设最大border长度是n-p, 另一个是n-q, 那么\gcd{(p,q)}是s的周期. 那么n-\gcd(p,q)也是一个border.

也就是说\gcd(p,q)=p, p|q 证毕.

然后我们发现就是整个字串的匹配一定是它自己或者它的一个border.

既然这些串可以相互表达, 那么, 如果一个小串可以表达一个长串, 那么长串一定不优, 舍去.

然后我们发现每一次长度就会减半...... 也就是说只有\lg{n}种不同的border, 它们的长度每个比另一个大一倍以上......

然后我们考虑找到那个是最优的.

我们从最小的开始向上......

每一次找到一个目前最小切可行的, 然后匹配当前的, 如果不行, 那么将当前的置为最优.

但是怎么检验能否覆盖呢? 字符串蛤希啊!

然后...... 差不多就是这样吧......

可能有一些难懂, 但是代码还是蛮简洁的......

那么放一下代码吧...... 很多思想和细节都在代码里面......

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
char huaji[500010];
int len, nex[500010];
unsigned long long haxi[500010], power[500010];
vector<int>borders;
int sum[500010];
int main() {
    gets(huaji + 1);
    len = strlen(huaji + 1);
    for (int i = 2; i <= len; i++) {
        nex[i] = nex[i - 1];
        while (nex[i] && huaji[nex[i] + 1] != huaji[i])nex[i] = nex[nex[i]];
        if (huaji[nex[i] + 1] == huaji[i])nex[i]++;
    }
    // 这一题并没有卡蛤希, 我们直接long long自然溢出就可以了
    power[0] = 1;
    for (int i = 1; i <= len; i++)power[i] = power[i - 1] * 19260817, haxi[i] = haxi[i - 1] * 19260817 + huaji[i];// 记住, 这是蛤希
    for (int i = len; i; i = nex[i])if (nex[i] * 2 < i)borders.emplace_back(i);// 这是一个**有用的**border
    reverse(borders.begin(), borders.end());
    int ans = borders[0];
    for (int i = 1; i <= borders.size() - 1; i++) {
        // 从小到大逐个比较, 尝试用当前最优的串去匹配当前串, 如果匹配失败, 那么舍弃之前的串, 使用现在的作为最优解(不是因为刺穿更优, 而是之前的串不行......)
        int cur = borders[i];
        memset(sum, 0, (cur + 10) * sizeof(int));
        sum[ans] = 1;
        for (int i = ans + 1; i <= cur; i++)sum[i] = sum[i - 1] + (haxi[i] - haxi[i - ans] * power[ans] == haxi[ans] && sum[i - 1] != sum[i - ans - 1]);
        // 使用蛤希匹配, 计算能否使用最优串匹配当前串
        if (sum[cur] == sum[cur - 1])ans = cur;
    }
    cout << ans;
}

跑的挺快的...... 其它题解没有见到, 所以这里简单地写一下......