参考文章: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);
}