题解：P6939 [ICPC 2017 WF] Tarot Sham Boast

· · 题解

声明：本篇题解使用 ABC 代替 PSR。

看到这个题，认为所有串出现的期望是一样的，实际上也确实。

但是，比如说 AAA 在 AAAA 中出现两次，只产生了 1 的贡献，这就产生了区别。

发现出现的这两次有重合，于是想到可以用 KMP 算法，求 border，然后对于 border 考虑。

border 越长越容易重，越容易重贡献就越小，所以按 border 长度排序，假了。

考虑 hack：ABACABA 和 ABBCAB，前者除了前后 3 位重叠，还有前后 1 位重叠的方式，所以应排在后面。

这个怎么做呢？

首先证明一个结论：一个串的 border 的 border 也是原串的公共前后缀，这句话可能有点难理解，举一个例子。

ABACABA 这个串，border 是 ABA，ABA 的 border 是 A，而 A 是 ABACABA 的公共前后缀，也就是它的前缀有 A 后缀也有 A。

理解了这个例子也就会证了，border 保证了前后相同，在前缀中前缀和后缀相同，那么在后缀中也是前缀和后缀相同。

故前缀的前缀和后缀的后缀相同。

知道了这个我们就可以快速求出串的所有公共前后缀。

发现这个位置是串 S 概率是什么，枚举一个位置，就要钦定后面的 len 位 (其中 len 为串长)，概率为 3^{-len}，发现和进制类似。

这个可以决定一件事，S 的一个大 border 比 T 的大，那么 T 有再多小 border 也不好使，也要排在 S 的前面。

发现这个像字典序于是直接存到 vector 里，利用 STL 偷懒。

然后就是你发现还过不了，因为 ABACABA，这个重叠 1 位拼起来，是 ABACABABACABA，巨长无比，可能比 n 还长，这个就要判一下，设当前 border 长为 l，那么有 2 \times len - l \le n。

最后还有一个样例 hack 不了的细节，就是输入的字符串长度不一定相同，这个时候短的一定会排在前面，显然。

排好序输出即可，具体实现可以参考代码，个人认为实现并不是这题的难点。

#include<bits/stdc++.h>
using namespace std;
int n,m;
string s[20],ss[20];
int fail[1000010];
int main(){
    cin>>n>>m;
    vector<pair<vector<int> , int>> ans;
    for(int p = 1;p<=m;p++){
        cin>>s[p];
        ss[p] = s[p];
        int len = s[p].size();
        s[p] = '_' + s[p];
        fail[1] = 0;
        for(int i = 2,j = 0;i<=len;i++){
            while(j != 0 && s[p][j + 1] != s[p][i])j = fail[j];
            if(s[p][j + 1] == s[p][i])j++;
            fail[i] = j;
        }
        int now = len;
        vector<int> t;
        while(now != 0){
            if(2 * len - now <= n){
                t.push_back(now);
            }
            now = fail[now];
        }
        ans.push_back({t , p}); 
    }
    sort(ans.begin() , ans.end());
    for(int i = 0;i<ans.size();i++){
        cout<<ss[ans[i].second]<<"\n";
    }
    return 0;
}