bzoj2946 [Poi2000]公共串

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

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;
}

相關文章

程式語言 最新文章