【BZOJ1622】[Usaco2008 Open]Word Power 名字的能量

2014-06-04
竞赛题解 / 模拟
BZOJUSACO

描述 Description

约翰想要计算他那 N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过 1000 个字待构成，没有一个名字是空字体串， 约翰有一张 “能量字符串表”，上面有 M(1≤M≤100) 个代表能量的字符串．每个字符串由不超过 30 个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不一定一个紧接着一个）．

所有的大写字母和小写字母都是等价的．比如，在贝茜的名字 “Bessie” 里，蕴含有 “Be”“sI”“EE” 以及 “Es” 等等字符串，但不蕴含 “lS” 或“eB”．请帮约翰计算他的奶牛的名字的能量．

输入格式 InputFormat

第 1 行输入两个整数 N 和 M，之后 N 行每行输入一个奶牛的名字，之后 M 行每行输入一个能量字符串．

输出格式 OutputFormat

一共 N 行，每行一个整数，依次表示一个名字的能量．

样例输入 SampleInput

10 8
Elhedsmjvktpfvmasaedymwxcbtlbmmcyjrdtuzmodkuugwopopezmkrrjqhyunpmduzoqxbbyc
Hdshtkfavmdpasterecuvhqgvzylbwlbbomelvccstxzovwmtrnubnlfjubatvszzyldyjwbzuxbvv
Ymapltdepedyiixbpeamirrnxptnwckdmbzuktpoodawgtbckzwhuayzct
Fgzsgzgiybjthasgbgrkxspzkhkwnmenrvnwlhdmteddaogebadfanekvikahrllzftrocvyzsgahkzftvxzdohhaxn
Fklycvmgelvdrhsfjyimnzuykdmlgikhymohhofuhwb
Lizjmgqjwnriduhrfussuvrswswruptgybqqfndixrtusrfdnvwhtdqgkzinzjqwvshihkv
Qzbdcvxhslplntfttvplbxkdoadservscmgbfz
Kkjkltrnitvcswwezdlztpcxsqqbdzrnxtmxjfbfmwq
Sottgyxvaazojfgisqditpbpxbafhobveflasfztdcf
Micmyadmbsunvsilsgvlnhzgjbvsudrffrcdiyigtwbitgpslgrrjnaksdxerdn
CV
VVdN
kF
CM
Aeyt
QVNg
NXhR
CilK

样例输出 SampleOutput

4
4
2
4
5
2
4
2
0
4

来源 Source

Silver

BZOJ 1622

代码 Code

每次用 f[i][j]表示被匹配串从第 i 位开始下一次出现字符 j 的位置。时间复杂度 O(NL1A+NML2), 其中 L1≤1000,A=26,L2≤30.

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char a[1005][1005];
char c[105][35];
int f[1005][200];
int i,j,t,n,m,l,r,k,z,y,x,s,ans;
void TEST()
{
    int i,j,t,k;
    for (i=1;i<=n;i++) cout<<a[i]+1<<" "<<strlen(a[i]+1)<<endl;
    for (i=1;i<=m;i++) cout<<c[i]+1<<endl;
    for (j=0;j<=strlen(a[i]+1);j++)
    {
        for (k=(int)'a';k<=(int)'z';k++) if (f[j][k]!=-1) cout<<""<<j<<" "<<(char)k<<" "<<f[j][k]<<endl;
    }
    cout<<endl;
}
int main()
{
    scanf("%d%dn",&n,&m);
    for (i=1;i<=n;i++) 
    {
        scanf("%s",a[i]+1);
        for (j=1;j<=strlen(a[i]+1);j++) if (a[i][j]<'a') a[i][j]='a'+a[i][j]-'A';
    }
    for (i=1;i<=m;i++)
    {
        scanf("%s",c[i]+1);
        for (j=1;j<=strlen(c[i]+1);j++) if (c[i][j]<'a') c[i][j]='a'+c[i][j]-'A';
    }
    for (i=1;i<=n;i++)
    {
        memset(f,-1,sizeof(f));
        for (j=strlen(a[i]+1);j>=0;j--)
        {
            memcpy(f[j],f[j+1],sizeof(f[0]));
            f[j][a[i][j+1]]=j+1;
        }
        ans=m;
        for (j=1;j<=m;j++)
        {
            t=0;
            for (k=1;k<=strlen(c[j]+1);k++)
            {
                if (f[t][c[j][k]]==-1)
                {
                    ans--;
                    break;
                }
                else
                {
                    t=f[t][c[j][k]];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}