JZOJ 2921 字符串识别

对 S 建 SAM，对 1≤i≤|S|，在 Parent Tree 上倍增求出 li=max{j∣|endpos(Sj…i)|=1}。

对于 1≤i≤|S|，若其存在，考虑其贡献。
显然对于 [li,i] 内的位置，都会造成 i−li+1 的贡献。将 i−li+1 从大到小排序，使用线段树或珂朵莉树实现区间覆盖即可；
而对于 j∈[1,li)，会造成 i−j+1 的贡献。这部分的贡献将 li 排序并使用双指针计算答案即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 5e5;
const int LG = 20;
int n;
int ed[N + 5],ans[N + 5];
char s[N + 5];
struct note
{
    int l,r;
    inline bool operator>(const note &o) const
    {
        return r - l > o.r - o.l;
    }
    inline bool operator<(const note &o) const
    {
        return l < o.l;
    }
} a[N + 5];
int seg[(N << 2) + 10];
inline void push(int p)
{
    if(seg[p])
    {
        seg[ls] = seg[rs] = seg[p];
        seg[p] = 0;
    }
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p] = k;
        return ;
    }
    push(p);
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,ls,tl,mid),1);
    r > mid && (update(l,r,k,rs,mid + 1,tr),1);
}
int query(int x,int p,int tl,int tr)
{
    if(tl == tr)
        return seg[p] ? seg[p] : n;
    push(p);
    int mid = tl + tr >> 1;
    return x <= mid ? query(x,ls,tl,mid) : query(x,rs,mid + 1,tr);
}
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int sz[(N << 1) + 5];
    int c[N + 5],a[(N << 1) + 5];
    int f[LG + 5][(N << 1) + 5];
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1,sz[p] = 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len],f[0][i] = sam[i].fa;
        for(register int i = 1;i <= LG;++i)
            for(register int j = 1;j <= tot;++j)
                f[i][j] = f[i - 1][f[i - 1][j]];
        for(register int i = 1;i <= n;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sz[sam[a[i]].fa] += sz[a[i]];
    }
}
int main()
{
    scanf("%s",s + 1),n = strlen(s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - 'a'),ed[i] = SAM::las,a[i].r = i;
    SAM::build();
    for(register int i = 1,p;i <= n;++i)
    {
        p = ed[i];
        for(register int j = LG;~j;--j)
            if(SAM::f[j][p] && SAM::sz[SAM::f[j][p]] <= 1)
                p = SAM::f[j][p];
        a[i].l = SAM::sz[p] <= 1 ? i - SAM::sam[SAM::sam[p].fa].len : -0x3f3f3f3f;
    }
    sort(a + 1,a + n + 1,greater<note>());
    for(register int i = 1;i <= n;++i)
        update(a[i].l,a[i].r,a[i].r - a[i].l + 1,1,1,n);
    sort(a + 1,a + n + 1);
    for(register int i = n,j = n,mn = 0x3f3f3f3f;i;--i)
    {
        for(;i <= a[j].l && j;mn = min(mn,a[j--].r));
        ans[i] = min(query(i,1,1,n),mn - i + 1);
    }
    for(register int i = 1;i <= n;++i)
        printf("%d\n",ans[i]);
}