[Usaco2008 Open]Word Power 名字的能量

1622: [Usaco2008 Open]Word Power 名字的能量

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 408 Solved: 198
[Submit][Status][Discuss]

Description

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

所有的大写字母和小写字母都是等价的．比如，在贝茜的名字“Bessie”里，蕴含有“Be”

“sI”“EE”以及“Es”等等字符串，但不蕴含“lS”或“eB”．请帮约翰计算他的奶牛的名字的能量．

Input

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

Output

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

Sample Input

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

INPUT DETAILS:

There are 5 cows, and their names are "Bessie", "Jonathan",
"Montgomery", "Alicia", and "Angola". The 3 good strings are "se",
"nGo", and "Ont".

Sample Output

1
1
2
0
1

OUTPUT DETAILS:

"Bessie" contains "se", "Jonathan" contains "Ont", "Montgomery" contains
both "nGo" and "Ont", Alicia contains none of the good strings, and
"Angola" contains "nGo".

HINT

Source

Silver

　　　　　　　　　　　　　　　　　　　　　　　　[Submit][Status][Discuss]

　　本来想找一道字符串的题，看着像是一道模拟，直接爆搜，但是超时了好几次。。。下面是两种写法，一个是6100多毫秒个计时器掐了，另一种却是200多毫秒AC。。。。

　　先来个超时的。。。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<bits/stdc++.h>

 using namespace std;

 int N,M;

 char T[][];

 char P[][];

 int lenT[];

 int lenP[];

 int main(){

     cin>>N>>M;

     for(int i=;i<=N;i++) scanf("%s",T[i]);

     for(int i=;i<=M;i++) scanf("%s",P[i]); 

     for(int i=;i<=N;i++){

         for(int j=;j<=strlen(T[i])-;j++){

             if(int(T[i][j])>=)

                 T[i][j]=char(int(T[i][j])-);

         }

     }

     for(int i=;i<=M;i++){

         for(int j=;j<=strlen(P[i])-;j++){

             if(int(P[i][j])>=)

                 P[i][j]=char(int(P[i][j])-);

         }

     }

     for(int i=;i<=N;i++){

         int ANS=;

         for(int j=;j<=M;j++){

             int now=;

             int len=strlen(P[j]);

             for(int k=;k<=strlen(T[i])-;k++){

                 if(T[i][k]==P[j][now]){

                     now++;

                     if(now==len){

                         ANS++;

                         break;

                     }

                 }

             }

         }

         cout<<ANS<<endl;

     }

     return ;

 }

　然后改成这个就AC了，至少快了30多倍。。。差别很大么？

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<bits/stdc++.h>

 using namespace std;

 int N,M;

 char T[][];

 char P[][];

 int lenT[];

 int lenP[];

 int main(){

     cin>>N>>M;

     for (int i=;i<=N;i++){

         scanf("%s",T[i]);

         while (T[i][lenT[i]])

         {

             if (int(T[i][lenT[i]])<)

                 T[i][lenT[i]]=char(int(T[i][lenT[i]])+);

             lenT[i]++;

         }

     }

     for (int i=;i<=M;i++){

         scanf("%s",P[i]);

         while(P[i][lenP[i]])

         {

             if(int(P[i][lenP[i]])<)

                 P[i][lenP[i]]=char(int(P[i][lenP[i]])+);

             lenP[i]++;

         }

     }

     for(int i=;i<=N;i++){

         int ANS=;

         for(int j=;j<=M;j++){

             int now=;

             for(int k=;k<=lenT[i]-;k++){

                 if(T[i][k]==P[j][now]){

                     now++;

                     if(now==lenP[j]){

                         ANS++;

                         break;

                     }

                 }

             }

         }

         cout<<ANS<<endl;

     }

     return ;

 }

巴特西