参考文章:https://segmentfault.com/a/1190000021980858
题目描述 :
兔子发现序列的名字都是数字,实在太无聊了,于是兔子开始研究兔子的名字。
现在兔子手上有 n 个名字 Ti 和 m 个可爱词汇Sj,兔子对每一个名字 Ti 定义了一个可爱度,如果 Ti 中出现了一个可爱的单词 Sj,那么 Ti 就有 1 点可爱值,最后的总可爱值就是 Ti 的可爱度,这里的出现指 Sj 是 Ti 的子序列。
例如 abc 是 aebdc 的子序列,abc 也是 abcd 的子序列。
现在兔子想知道每一个名字的可爱度
输入描述:
第 1 行两个整数 n 和 m,表示名字个数和可爱词汇个数。
接下来 n 行,第 i 行是字符串 Ti ,表示兔子手里的名字。
再接下来 m 行,每行一个字符串 Sj ,表示兔子手里的可爱词汇。
输出描述:
输出共 n 行,每行一个整数,表示每一个名字的可爱度。
题解:
看了题目的标签写的是dp而且还要优化,但是我还不会,就上网看了其他的解法,用string,find()之类的都直接忽视了,然后看到一篇博客上,用的是子序列自动机,没学过但感觉挺厉害了。就上网搜了下,怎么写。ta的思路是,用个2维数组nxt[i][j]//初始化都为-1 ,表示第行开始,第j+'A'字符的最近位置。上面的参考文章我感觉讲的很清楚。初始化,就是从下往上,从右往左更新。
查找的话,就找f[i][ch-'A']是否为-1,不是就令i=f[i][ch-'A'],继续往下找。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; struct sqeum{ //26 characters int nxt[maxn][58]; //ascii(A)=65 ,ascii(a)=97, 58=122-65+1 // void buld(char *s) { int len=strlen(s+1); memset(nxt[len],0,sizeof(nxt[len])); for(int i=len;i>0;i--) { //从小往上,从右往左更新。时间复杂度O(len(s)*26+len(s)) for(int j=0;j<58;j++) nxt[i-1][j]=nxt[i][j]; nxt[i-1][s[i]-'A']=i; } } // int solve(char *t) { int len=strlen(t+1); int p=0;// root for(int i=1;i<=len;i++) { if(!nxt[p][t[i]-'A']){ //cout<<"NO"<<endl; return 0; } p=nxt[p][t[i]-'A']; } //cout<<"YES"<<endl; return 1; } }; int main() { int n,m; cin>>n>>m; char s[1000][105],t[100][35]; for(int i=0;i<n;i++) scanf("%s",s[i]+1); for(int i=0;i<m;i++) scanf("%s",t[i]+1); for(int i=0;i<n;i++) { int ans=0; sqeum sq; sq.buld(s[i]); for(int j=0;j<m;j++) ans+=sq.solve(t[j]); cout<<ans<<endl; } return(0); }