请求加强数据
查看原帖
请求加强数据
685993
Akagi_shigeru楼主2024/1/8 14:47
#include<bits/stdc++.h>
using namespace std;
namespace my_IO{
    #define ll long long
    #define ull unsigned long long
    #define ld long double
    #define et putchar('\n')
    #define spc putchar(' ')
    template<class T>
    void read(T &num){
        T x=0,f=1;
        char c=getchar();
        while(!isdigit(c)){
            if(c=='-') f=-1;
            c=getchar();
        }
        while(isdigit(c)){
            x=(x<<3)+(x<<1)+c-48;
            c=getchar();
        }
        num=f*x;
    }
    template<class T>
    void write(T x){
        static char buf[40];
        static int len=-1;
        if(x<0) putchar('-'),x=-x;
        do{
            buf[++len]=x%10+48;
            x/=10;
        }while(x);
        while(len>=0) putchar(buf[len--]);
    }
}
using namespace my_IO;
const int maxn=1e6+10;
int n,cnt,lst,head[maxn<<1],tot,siz[maxn<<1];
struct edge{
    int t,nxt;
}e[maxn<<1];
void add(int st,int ed){
    e[++tot]={ed,head[st]};
    head[st]=tot;
}
void dfs(int u){
    if(!head[u]){
        siz[u]=1;
        return;
    }
    for(int i=head[u];i;i=e[i].nxt){
        dfs(e[i].t);
        siz[u]+=siz[e[i].t];
    }
}
struct node{
    int len,link;
    map<char,int> to;
}sam[maxn<<1];
void init(){
    cnt=0;
    sam[0].link=-1;
}
void insert(char c){
    int cur=++cnt,p=lst;
    while(p!=-1&&!sam[p].to[c]){
        sam[p].to[c]=cur;
        p=sam[p].link;
    }
    if(p==-1){
        lst=cur;
        return;
    }
    int q=sam[p].to[c];
    if(sam[q].len==sam[p].len+1){
        sam[cur].link=q;
        lst=cur;
        return;
    }
    int clone=++cnt;
    sam[clone].to=sam[q].to;
    sam[clone].link=sam[q].link;
    sam[clone].len=sam[p].len+1;
    sam[cur].link=sam[q].link=clone;
    while(p!=-1&&sam[p].to[c]==q){
        sam[p].to[c]=clone;
        p=sam[p].link;
    }
    lst=cur;
}
void build(string s){
    for(auto c:s) insert(c);
}
int main(){
    string s;
    cin>>s;
    build(s);
    for(int i=1;i<=cnt;i++) add(sam[i].link,i);
    dfs(0);
    ll ans=0;
    for(int i=1;i<=cnt;i++) ans=max(ans,1ll*sam[i].len*siz[i]);
    write(ans);
}

这份代码既没有对 cur 节点的 len 赋值,也没有判断 siz>1siz>1。它居然过了。

2024/1/8 14:47
加载中...