POJ-2774 Long Long Message (最长公共子串，后缀系列结构)

后缀数组

将两个串接在一起，中间加上一些奇怪的字符

然后就是求下标分别落在两个串中的所有\(i,j\)中\(LCP(Suf_i,Suf_j)\)的最大值

按照\(SA\)的顺序可以发现只用考虑最近的\(i,j\)，所以对于每个 \(i\) 找到最近的 \(j\) 即可，就是一个尺取

尺取\(L,R\)之后可以用单调队列查询

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;

#define reg register
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
    int s=0;
    int f=0;
    while(!isdigit(IO=getchar())) f|=(IO=='-');
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}


const int N=2e5+10,INF=1e9;

int n,m;
char s[N];
int cnt[N],tmp[N],rk[N<<1],lcp[N],sa[N];

void PreMake(){
    memset(cnt,0,800);
    rep(i,1,n) cnt[(int)s[i]]++;
    rep(i,1,200) cnt[i]+=cnt[i-1];
    rep(i,1,n) rk[i]=cnt[(int)s[i]],sa[i]=i;
    rep(i,n+1,n*2) rk[i]=0;
    for(reg int k=1;k<=n;k<<=1) {
        rep(i,0,n) cnt[i]=0;
        rep(i,1,n) cnt[rk[i+k]]++;
        rep(i,1,n) cnt[i]+=cnt[i-1];
        drep(i,n,1) tmp[cnt[rk[i+k]]--]=i;
        
        rep(i,0,n) cnt[i]=0;
        rep(i,1,n) cnt[rk[i]]++;
        rep(i,1,n) cnt[i]+=cnt[i-1];
        drep(i,n,1) sa[cnt[rk[tmp[i]]]--]=tmp[i];
        
        rep(i,1,n) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+k]!=rk[sa[i-1]+k]);
        rep(i,1,n) rk[i]=tmp[i];
    }
    int h=0;
    rep(i,1,n) {
        int j=sa[rk[i]-1];
        if(h) h--;
        while(i+h<=n && j+h<=n && s[i+h]==s[j+h]) h++;
        lcp[rk[i]-1]=h;
    }
}

int GetIndex(int x) {
    x=sa[x];
    if(x<=m) return 1;
    if(x>m+1) return 2;
    return 0;
}

int c[4];
int Q[N],l=1,r;


int main(){
    scanf("%s",s+1),m=strlen(s+1);
    s[m+1]='#';
    scanf("%s",s+m+2),n=strlen(s+1);
    PreMake();
    int ans=0;
    for(reg int L=1,R=1;R<=n;++R) {
        c[GetIndex(R)]++;
        if(R-1>=L) {
            while(l<=r && lcp[Q[r]]>lcp[R-1]) r--;
            Q[++r]=R-1;
        }
        while(!GetIndex(L)||c[GetIndex(L)]>1) --c[GetIndex(L++)] ;
        while(l<=r && Q[l]<L) l++;
        if(c[1]&&c[2]) cmax(ans,lcp[Q[l]]);
    } // 尺取L,R 单调队列维护查询
    printf("%d\n",ans);
}

\[ \ \]

后缀自动机

当然可以像类似上面那样地去做，但是会比较慢，内存也会大

可以对于第一个串构建自动机，第二个串对于每个前缀，直接逐个匹配最长公共的的后缀

也就是逐个字符转移下来，如果不存在转移就不断返回\(link\)，直到存在转移或为空，注意同时维护当前长度

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=2e5+10;

bool be;

int n;
char s[N];
int trans[N][26];
int lst,stcnt;
int len[N],link[N],ma[N];

struct Edge{
    int to,nxt;
}e[N];
int head[N],ecnt;
void AddEdge(int u,int v) {
    ecnt++;
    e[ecnt].to=v,e[ecnt].nxt=head[u];
    head[u]=ecnt;
}

ll ans;
int vis[N];

bool ed;

void Init(){ 
    link[0]=-1,len[0]=0;
    rep(i,0,stcnt) {
        len[i]=head[i]=ma[i]=0;
        rep(j,0,25) trans[i][j]=0;
        vis[i]=0;
    }
    stcnt=lst=ecnt=0;
}

void Extend(int c) {
    int cur=++stcnt,p=lst;
    len[cur]=len[lst]+1;
    while(~p && !trans[p][c]) trans[p][c]=cur,p=link[p];
    if(p==-1) link[cur]=0;
    else {
        int q=trans[p][c];
        if(len[q]==len[p]+1) link[cur]=q;
        else {
            int clone=++stcnt;
            link[clone]=link[q];
            memcpy(trans[clone],trans[q],104);
            len[clone]=len[p]+1;
            while(~p && trans[p][c]==q) trans[p][c]=clone,p=link[p];
            link[q]=link[cur]=clone;
        }
    }
    lst=cur;
}


int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    Init();
    rep(i,1,n) Extend(s[i]-'a');
    int ans=0;
    scanf("%s",s+1);
    int len=strlen(s+1);
    int p=0,nowlen=0;
    rep(i,1,len) {
        int c=s[i]-'a';
        while(p && !trans[p][c]) {
            p=link[p];
            cmin(nowlen,(~p?::len[p]:0));
        }
        if(trans[p][c]) {
            p=trans[p][c];
            nowlen++;
        }
        cmax(ans,nowlen);
    }
    printf("%d\n",ans);
}

POJ-2774 Long Long Message (最长公共子串，后缀系列结构)

原文：https://www.cnblogs.com/chasedeath/p/12213441.html