bzoj Luogu https://www.luogu.com.cn/problem/P4112
题解时间
给两个小写字母串 $ A $ , $ B $ , 请你计算:
(1) $ A $ 的一个最短的子串, 它不是 $ B $ 的子串
(2) $ A $ 的一个最短的子串, 它不是 $ B $ 的子序列
(3) $ A $ 的一个最短的子序列, 它不是 $ B $ 的子串
(4) $ A $ 的一个最短的子序列, 它不是 $ B $ 的子序列
水题四合一, 一题更比四题 sao
首先由于都是要从 $ A $ 中找, 所以按照套路是把 $ A $ 在 $ B $ 上匹配
所以先构建出 $ B $ 的 SAM 和序列自动机.
序列自动机: 就是一个 $ next[i][ch] $ 数组表示第 $ i $ 位往后第一个出现字符 $ ch $ 的位置, 纯粹用来匹配的.
(1) 直接以 $ A $ 每一位为起点在 $ B $ 的 SAM 上暴力匹配, 只要失配就更新答案然后跳出.
(2) 换成在序列自动机上.
(3) $ dp[i][j] $ 表示 $ A $ 的前 $ i $ 个字符形成的子序列在 $ B $ 的 SAM 上匹配到了 $ j $ 位置, 此时形成的最短子序列长度, 这是个挺经典的 dp 了.
(4) 换成在序列自动机上.
- #include<bits/stdc++.h>
- using namespace std;
- namespace RKK
- {
- const int N=2011,inf=0x3f3f3f3f;
- int n1;char s1[N];
- int n2;char s2[N];
- struct remilia{int tranc[26],len,pre;};
- struct sakuya
- {
- remilia s[N<<1];
- int fin,size;
- sakuya(){fin=size=1;}
- void ins(int ch)
- {
- int npx,npy,lpx,lpy;
- npx=++size;
- s[npx].len=s[fin].len+1;
- for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;
- if(!lpx) s[npx].pre=1;
- else
- {
- lpy=s[lpx].tranc[ch];
- if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;
- else
- {
- npy=++size;
- s[npy]=s[lpy];
- s[npy].len=s[lpx].len+1;
- s[lpy].pre=s[npx].pre=npy;
- while(s[lpx].tranc[ch]==lpy)
- {
- s[lpx].tranc[ch]=npy;
- lpx=s[lpx].pre;
- }
- }
- }
- fin=npx;
- }
- void insert(char *str,int sl)
- {
- for(int i=1;i<=sl;i++)
- ins(str[i]-'a');
- }
- }sam;
- struct flandre
- {
- int ne[N][26],tmp[26];
- void insert(char *s,int sl)
- {
- for(int i=sl;i>=0;i--)
- memcpy(ne[i],tmp,104),tmp[s[i]-'a']=i;
- }
- }sem;
- void solve1()
- {
- int ans=inf;
- for(int sp=1;sp<=n1;sp++)
- {
- int px=1;
- for(int i=sp;i<=n1;i++)
- {
- if(!sam.s[px].tranc[s1[i]-'a']){ans=min(ans,i-sp+1);break;}
- px=sam.s[px].tranc[s1[i]-'a'];
- }
- }
- printf("%d\n",ans==inf?-1:ans);
- }
- void solve2()
- {
- int ans=inf;
- for(int sp=1;sp<=n1;sp++)
- {
- int px=0;
- for(int i=sp;i<=n1;i++)
- {
- if(!sem.ne[px][s1[i]-'a']){ans=min(ans,i-sp+1);break;}
- px=sem.ne[px][s1[i]-'a'];
- }
- }
- printf("%d\n",ans==inf?-1:ans);
- }
- int dp[N<<1];
- void solve3()
- {
- int ans=inf;
- memset(dp,0x3f,sizeof(dp));
- dp[1]=0;
- for(int i=1;i<=n1;i++)
- {
- for(int x=sam.size;x;x--)
- {
- if(sam.s[x].tranc[s1[i]-'a']) dp[sam.s[x].tranc[s1[i]-'a']]=min(dp[sam.s[x].tranc[s1[i]-'a']],dp[x]+1);
- else ans=min(ans,dp[x]+1);
- }
- }
- printf("%d\n",ans==inf?-1:ans);
- }
- void solve4()
- {
- int ans=inf;
- memset(dp,0x3f,sizeof(dp));
- dp[0]=0;
- for(int i=1;i<=n1;i++)
- {
- for(int x=n2;x>=0;x--)
- {
- if(!sem.ne[x][s1[i]-'a']) ans=min(ans,dp[x]+1);
- else dp[sem.ne[x][s1[i]-'a']]=min(dp[sem.ne[x][s1[i]-'a']],dp[x]+1);
- }
- }
- printf("%d\n",ans==inf?-1:ans);
- }
- int Iris()
- {
- scanf("%s%s",s1+1,s2+1),n1=strlen(s1+1),n2=strlen(s2+1);
- sam.insert(s2,n2),sem.insert(s2,n2);
- solve1(),solve2(),solve3(),solve4();
- return 0;
- }
- }
- int main(){return RKK::Iris();}
来源: http://www.bubuko.com/infodetail-3344098.html