這其實(shí)是道水題。。。

題目鏈接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4032

(luogu)https://www.luogu.org/problemnew/show/P4112

題解:

Task 1

\(O(n^2)\)做法無數(shù)(也有不用SAM的\(O(n^2)\)做法)，我講一下我的做法。

直接對B串建后綴自動機(jī)，用A串在上面跑，而且是像求兩個(gè)串的最長公共子串那樣跑，如果遇到失配了就拿當(dāng)前長度\(+1\)更新答案。但是要注意失配后當(dāng)前的長度不能設(shè)成當(dāng)前節(jié)點(diǎn)的\(len\)(最大長度)，而應(yīng)該是\(len[fail[u]]+1\)(最小長度)。

時(shí)間復(fù)雜度\(O(n)\).

由于沒有在網(wǎng)上看到\(O(n)\)做法，所以此做法正確性未知(能過，但是數(shù)據(jù)很水，一開始寫成\(len\)了依然能過10個(gè)點(diǎn)中的9個(gè))。

Task 2

設(shè)\(nxt[i][j]\)表示B序列中第\(i\)個(gè)位置之后最靠前的字符\(j\)的位置。枚舉A子串的起始位置，貪心即可。

時(shí)間復(fù)雜度\(O(n^2)\).

聽說有人把這個(gè)東西稱作“序列自動機(jī)”，感覺也有道理啊，這玩意確實(shí)像個(gè)自動機(jī)。

Task 3

子串就用后綴自動機(jī)，子序列就用“序列自動機(jī)”美滋滋。

設(shè)\(dp[i][j]\)表示A串前\(i\)個(gè)位置匹配B串后綴自動機(jī)的節(jié)點(diǎn)\(j\)，最少用多少長度。如果能轉(zhuǎn)移就轉(zhuǎn)移，不能轉(zhuǎn)移就用\(dp[i][j]+1\)更新答案。注意要在每個(gè)\(i\)都更新(因?yàn)樽有蛄锌梢圆坏筋^)。

然后第一維可以像01背包一樣省掉，我覺得第二維要按先兒子后父親的順序循環(huán)。但是網(wǎng)上有人直接從\(1\)到\(siz\)循環(huán)也能過？

注意\(dp\)數(shù)組要開兩倍。

Task 4

設(shè)\(dp[I][j]\)表示A串前\(i\)個(gè)位置匹配B串前\(j\)個(gè)位置的最小長度。

轉(zhuǎn)移同Task 3. 如果用一維數(shù)組，從\(n\)到\(1\)循環(huán)。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 2000; const int S = 26; int len[(N<<1)+3]; int fa[(N<<1)+3]; int son[(N<<1)+3][S+3]; char a[N+3],b[N+3]; int pos[S+3]; int nxt[N+3][S+3]; int dp[(N<<1)+3]; int ord[(N<<1)+3]; int buc[N+3]; int n,m,siz,rtn,lstpos;void initSAM() {siz = rtn = lstpos = 1; }void insertchar(char ch) {int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1;for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}if(!p) {fa[np] = rtn;}else{int q = son[p][ch];if(len[p]+1==len[q]) {fa[np] = q;}else{siz++; int nq = siz; len[nq] = len[p]+1;memcpy(son[nq],son[q],sizeof(son[q]));fa[nq] = fa[q]; fa[np] = fa[q] = nq;for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}}} }void update(int &x,int y) {x = min(x,y);}int main() {initSAM();scanf("%s",a+1); n = strlen(a+1); for(int i=1; i<=n; i++) a[i] -= 96;scanf("%s",b+1); m = strlen(b+1); for(int i=1; i<=m; i++) b[i] -= 96;for(int i=1; i<=m; i++){insertchar(b[i]);}for(int i=1; i<=m; i++){for(int j=pos[b[i]]; j<i; j++){nxt[j][b[i]] = i;}pos[b[i]] = i;}for(int i=1; i<=S; i++){for(int j=0; j<=m; j++) {if(!nxt[j][i]) nxt[j][i] = m+1;}}for(int i=1; i<=siz; i++) buc[len[i]]++;for(int i=1; i<=n; i++) buc[i] += buc[i-1];for(int i=siz; i>=1; i--) ord[buc[len[i]]--] = i;//Question 1int u = rtn,cur = 0,ans1 = m+1;for(int i=1; i<=n; i++){while(u && son[u][a[i]]==0) {ans1 = min(ans1,cur+1); u = fa[u]; cur = len[fa[u]]+1;}if(son[u][a[i]]!=0) {cur++; u = son[u][a[i]];}else {ans1 = 1; u = rtn; cur = 0;}}if(ans1==m+1) printf("-1\n");else printf("%d\n",ans1);//Question 2int ans2 = n+1;for(int i=1; i<=n; i++){int j = 0;for(int k=i; k<=n; k++){if(nxt[j][a[k]]<=m){j = nxt[j][a[k]];}else{ans2 = min(ans2,k-i+1);}}}if(ans2==n+1) printf("-1\n");else printf("%d\n",ans2);//Question 3int ans3 = n+1;for(int i=1; i<=siz; i++) dp[i] = n+1; dp[rtn] = 0;for(int i=1; i<=n; i++){for(int j=siz; j>=1; j--){int u = ord[j];if(son[u][a[i]]){update(dp[son[u][a[i]]],dp[u]+1);}else{update(ans3,dp[u]+1);}}}if(ans3==n+1) printf("-1\n");else printf("%d\n",ans3);//Question 4int ans4 = n+1;for(int i=1; i<=n; i++) dp[i] = n+1; dp[0] = 0;for(int i=1; i<=n; i++){for(int j=m; j>=0; j--){if(nxt[j][a[i]]<=m){update(dp[nxt[j][a[i]]],dp[j]+1);}else{update(ans4,dp[j]+1);}}}if(ans4==n+1) printf("-1\n");else printf("%d\n",ans4);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4032 luogu P4112 [HEOI2015]最短不公共子串 (DP、后缀自动机)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。