题意

给定一个只包含小写字母的字符串\(S\),

请你求出 \(S\) 的所有出现次数不为 \(1\) 的子串的出现次数乘上该子串长度的最大值。

对于\(100\%\) 的数据，\(|S| \leq 10^6\)

分析

后缀自动机和拓扑序的裸题。

对一个节点而言，其后每可转移到一个可接受的节点，标志着该节点对应的子串出现次数加1。

处理顺序需要可转移到的节点都被处理到，所以拓扑排序就好了。

时间复杂度\(O(|S|)\)

代码

#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#define rg register
#define il inline
#pragma GCC optimize ("O3")
using namespace std;
template<class T> inline T read(T&x)
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=10*data+ch-'0',ch=getchar();
    return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;

const int MAXN=1e6+7;
int n;
char s[MAXN];

const int CHARSET_SIZE=26;
struct node
{
    int ch[CHARSET_SIZE],fa,len;
};

struct SufAuto
{
    node t[MAXN<<1];
    int cnt[MAXN<<1];
    int sz,root,last;

    il int newnode(rg const int&x)
    {
        t[++sz].len=x;
        return sz;
    }

    il void init()
    {
        memset(cnt,0,sizeof cnt);
        sz=0;
        root=last=newnode(0);
    }

    il void extend(rg const int&c)
    {
        rg int v = last,u = newnode(t[v].len + 1);

        for(;v && !t[v].ch[c];v = t[v].fa)
            t[v].ch[c] = u;

        if(!v)
        {
            t[u].fa=root;
        }
        else
        {
            rg int o = t[v].ch[c];
            if(t[o].len == t[v].len+1)
            {
                t[u].fa = o;
            }
            else
            {
                rg int n = newnode(t[v].len + 1);
                copy(t[o].ch,t[o].ch+CHARSET_SIZE,t[n].ch);
                t[n].fa = t[o].fa;
                t[o].fa = t[u].fa = n;
                for(;v && t[v].ch[c] == o;v = t[v].fa)
                    t[v].ch[c] = n;
            }
        }

        cnt[u]=1;
        last = u;
    }

    int a[MAXN<<1],c[MAXN];
    il void rdxsort()
    {
        memset(c,0,sizeof c);
        for(rg int i=1;i<=sz;++i)
            ++c[t[i].len];
        for(rg int i=1;i<=n;++i)
            c[i]+=c[i-1];
        for(rg int i=sz;i>=1;--i)
            a[c[t[i].len]--]=i;
    }

    il int solve()
    {
        rg ll ans=0;
        for(rg int i=sz;i>=1;--i)
        {
            rg int p=a[i];
            cnt[t[p].fa]+=cnt[p];
            if(cnt[p]>1)
                ans=max(ans,(ll)cnt[p]*t[p].len);
        }
        return ans;
    }
}T;

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%s",s);
    n=strlen(s);
    T.init();
    for(rg int i=0;i<n;++i)
        T.extend(s[i]-'a');
    T.rdxsort();
    printf("%d\n",T.solve());
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

巴特西

LG3804 【模板】后缀自动机

题意

分析

代码

最新文章

热门文章