CF427D Match & Catch

FxorG · 2021-07-08 09:58:16 · 个人记录

\text{Solution}

建广义SAM，考虑 len_{min}v=len_{max}u+1(u是v的父亲)。

再开2个计数器就好了。

\text{Code}

// SB题 两边都出现就同SAM不同计数器 
// O(n) n>m
#include <bits/stdc++.h>

#define N (int)(5e4+5)

using namespace std;

struct edge {
    int nex,to;
}e[N]; 

int head[N],cnt;
char s1[N],s2[N];
int fa[N],sz1[N],sz2[N],son[26][N],len[N];
int n,m,las=1,tot=1;

void ins(int c,int *sz) {
    int pre=las,x=++tot; las=x; len[x]=len[pre]+1; sz[x]=1;
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=1;
    else if(len[y]==len[pre]+1) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    }
/*  x=las;
    while(x&&sz[x]<=1) ++sz[x],x=fa[x];*/
}

void add_edge(int x,int y) {
    e[++cnt]=edge{head[x],y};
    head[x]=cnt;
} 

void dfs(int x) {
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        dfs(y); sz1[x]+=sz1[y]; sz2[x]+=sz2[y];
    }
}

int main() {
    scanf("%s%s",s1+1,s2+1);
    n=strlen(s1+1); m=strlen(s2+1);
    for(int i=1;i<=n;i++) ins(s1[i]-'a',sz1);
    las=1; for(int i=1;i<=m;i++) ins(s2[i]-'a',sz2);
    for(int i=2;i<=tot;i++) add_edge(fa[i],i);
    dfs(1);
    int ans=0x7fffffff;
    for(int i=2;i<=tot;i++) if(sz1[i]==1&&sz2[i]==1) ans=min(ans,len[fa[i]]+1);
    printf("%d",ans>=0x7ffffff?-1:ans);
    return 0;
}