P8617 [蓝桥杯 2014 国 AC] 重复模式 题解

· · 题解

题目描述不是很清晰，实际上 S 只由小写字母构成。

先说一下部分分做法，考虑二分，二分长度，利用 hash 和 map 来进行复杂度为 O(n \log n) 的比较判断，总复杂度 O(n \log ^ 2n)。由于单 hash 的 hash 冲突比较严重，而双 hash 效率又太慢，故使用这个办法本人只获得了 60。

考虑使用 SAM 求出来所有子串的出现次数和长度，如果一个子串出现了 2 次以上，则对答案进行一次贡献，复杂度 O(n \log n)。


#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define For(i, j, n) for(register int i = j ; i <= n ; ++i)
int ans, cnt, len, last;
int a[N], l[N], fa[N], go[N][26], siz[N];
string s;

inline void insert(int x){
    int p = last, np = ++cnt;
    last = np, siz[np] = 1, l[np] = l[p] + 1; 
    for( ; !go[p][x] && p ; p = fa[p]) go[p][x] = np;
    if(!p) return fa[np] = 1, void();
    int nq = go[p][x];
    if(l[nq] == l[p] + 1) fa[np] = nq;
    else{
        int q = ++cnt;
        fa[q] = fa[nq], fa[nq] = fa[np] = q;
        l[q] = l[p] + 1;
        memcpy(go[q], go[nq], sizeof(go[nq]));
        for( ; go[p][x] == nq ; p = fa[p]) go[p][x] = q;
    }
}

inline bool cmp(int x, int y){ return l[x] > l[y]; }
int main(){
    cin >> s, cnt = last = 1;
    for(auto i : s) insert(i - 'a');
    For(i, 1, cnt) a[i] = i;
    sort(a + 1, a + cnt + 1, cmp);
    For(i, 1, cnt){
        siz[fa[a[i]]] += siz[a[i]];
        if(siz[a[i]] > 1) ans = max(ans, l[a[i]]); 
    }
    printf("%d", ans);
    return 0;
}