bzoj2946 [Poi2000]公共串

NO IMAGE

Description


給出幾個由小寫字母構成的單詞,求它們最長的公共子串的長度。

任務:

    讀入單詞
    計算最長公共子串的長度
    輸出結果

1<=n<=5
單詞只由小寫字母組成,長度至少為1,最大為2000。

Solution


我好弱啊,寫完搜題解才發現可以巧妙地hash 二分

回憶一下兩個串的時候把第一個建sam第二個扔上去跑,記錄每一個節點向前能取到的最長長度,取max就是答案了(根據sam的定義)

那麼多個串就同理,把第一個建sam剩下的分別扔上去跑。用tmp[j][i]記錄當前串節點i能向前拓展最長長度,f[j][i]記錄前j個串節點i向前拓展最長長度,顯然可以用tmp更新f然後出答案

Code


#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
#define fill(x,t) memset(x,t,sizeof(x))
#define copy(x,t) memcpy(x,t,sizeof(x))

const int N=200005;

int rec[N][26],fa[N],len[N];
int tmp[N],f[N];
int last,cnt;
bool vis[N];
char str[6][N];

void extend(char ch) {
    int p,q,np,nq;
    p=last; last=np=  cnt;
    while (p&&!rec[p][ch]) {
        rec[p][ch]=np;
        p=fa[p];
    }
    if (!p) fa[np]=1;
    else {
        q=rec[p][ch];
        if (len[p] 1==len[q]) fa[np]=q;
        else {
            int nq=  cnt; len[nq]=len[p] 1;
            copy(rec[nq],rec[q]);
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            while (p&&rec[p][ch]==q) {
                rec[p][ch]=nq;
                p=fa[p];
            }
        }
    }
}

void solve(char *str) {
    fill(tmp,0);
    int now=1,l=0;
    rep(i,0,strlen(str)-1) {
        while (now&&!rec[now][str[i]-'a']) {
            now=fa[now];
            l=len[now];
            vis[now]=1;
            tmp[now]=std:: max(tmp[now],l);
        }
        if (!now) {
            now=1;
            l=0;
        }
        now=rec[now][str[i]-'a'];
        l  ;
        vis[now]=1;
        tmp[now]=std:: max(tmp[now],l);
    }
    rep(i,1,cnt) f[i]=std:: min(f[i],tmp[i]);
}

int main(void) {
    int n; scanf("%d",&n);
    rep(i,1,n) scanf("%s",str[i]);
    cnt=last=1;
    rep(i,0,strlen(str[1])-1) extend(str[1][i]-'a');
    fill(f,31);
    rep(i,2,n) solve(str[i]);
    int ans=0;
    rep(i,1,cnt) ans=std:: max(ans,f[i]);
    printf("%d\n", ans);
    return 0;
}