洛谷P3804 后缀自动机 (SAM)

// https://www.luogu.com.cn/problem/P3804

#include <algorithm> 

#include <cstdio> 

#include <iostream>

#include <vector>

#include <cstring>

#include <queue>

#define maxn 2000005

using namespace std;

struct node{

int ch[26];

int len,fa;

}a[maxn];

int num=1;

int np=1;

bool prefix[maxn]; // if it contains a prefix

void add(int c){

int p=np;np=++num;

prefix[np] = true;

a[np].len=a[p].len+1;

for(;p&&!a[p].ch[c];p=a[p].fa) a[p].ch[c]=np;

if(!p) a[np].fa=1;

else{

int q=a[p].ch[c];

if(a[q].len==a[p].len+1){ a[np].fa=q;

cout<<"  p="<<p<<" q="<<q<<"   a[p].len="<<a[p].len<<"   a[q].len="<<a[q].len<<"  np="<<np<<" a[np].fa="<<a[np].fa<<endl;

}

else{

int nq=++num;

a[nq]=a[q];

a[nq].len=a[p].len+1;

a[q].fa=a[np].fa=nq;

cout<<"  p="<<p<<" q="<<q<<"   a[p].len="<<a[p].len<<"   a[q].len="<<a[q].len<<" nq="<<nq<<"   a[nq].len="<<a[nq].len<<"  np="<<np<<" a[np].fa="<<a[np].fa<<endl;

for(;p&&a[p].ch[c]==q;p=a[p].fa) a[p].ch[c]=nq;

}

}

}

int siz[maxn]; // size of endpos

int deg[maxn];  

queue< int > q;  

void solve(){

while(!q.empty()) q.pop();

memset(deg,0,(num+1)<<2);

for(int i=1; i<=num; ++i)  

++ deg[a[i].fa], siz[i] = 0;

 

for(int i=1; i<=num; ++i)

{

cout<< deg[i]<<"=deg[i], i= "<<i<<endl;

}

for(int i=1; i<=num; ++i)

if(!deg[i]) q.push(i);

while(!q.empty()){

int x = q.front(); q.pop();

if(prefix[x]) 

++ siz[x];

if(a[x].fa == 1) continue;

siz[a[x].fa] += siz[x]; // transfer

if((-- deg[a[x].fa]) == 0)

q.push(a[x].fa);

}

long long ans = 0; // int overflow

for(int i=1; i<=num; ++i)

if(siz[i] > 1) // not only once

{

ans = max(ans,1ll*a[i].len*siz[i]);

cout<<i<<"=i,"<<a[i].len<<"=len,  siz[i]="<<siz[i]<<endl;

}

printf("%lld\n",ans);

}

char s[maxn]="aaba";

int main(){

//scanf("%s",s);

int len=strlen(s);

for(int i=0;i<len;i++) {

add(s[i]-'a');

cout<<"  i="<<i+1<<" s[i]="<<s[i]<<endl;

}

for(int i=1;i<=num;i++) {

cout<<"  i="<<i<<"  a[i].len="<<a[i].len<<"     a[i].fa="<<a[i].fa<<" prefix="<<prefix[i]<<endl;

}

solve();

return 0;

}