【jzoj2403】【2012.02.25普及組】單詞（word）

題目描述

FJ想計算他的N(1<=N<=1000)隻奶牛的名字的好聽度，每個奶牛的名字是一個長度不超過1000的英文字母串。他建立了一個好名字的集合，數量為M(1<=M<=100)，每個好名字的長度不超過30，奶牛的名字中每包含一個好名字(“包含”不一定要求連續)，那麼它的好聽度就加1。所有的名字都不區分大小寫，如名字“Bessie”包含“Be”、“sI”、“EE”、“Es”,但是不包含“eB”。

現在請你幫FJ計算每個奶牛名字的好聽度。

輸入

第1行: 2個用空格隔開的整數N 和 M；

第2…N+1行: 第i+1行為第i個奶牛的名字；

第N+2…N+M+1行：第N+i+1行為第i個好名字。

輸出

第1…N行：第i個數為第i頭奶牛名字的好聽度。

樣例輸入

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont
           

樣例輸出

1
1
2
0
1
           

提示

輸入說明：FJ有5頭奶牛，名字依次為"Bessie", “Jonathan”,“Montgomery”, Alicia"和"Angola"，有3個好名字分别為"se","nGo"和 “Ont”.

輸出說明: “Bessie” 包含 “se”, “Jonathan"包含"Ont”, "Montgomery"包含 “nGo” 、“Ont”，”Alicia“不包含任何好名字，“Angola"包含"nGo”.

解題思路

暴力對比，三個for：第一層枚舉奶牛名字，第二層枚舉好名字，第三層比較奶牛名字裡有沒有好名字

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int n,m,Gun;
string a[2000],b[200];
int main(){
	freopen("word.in","r",stdin);
	freopen("word.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=0;j<a[i].size();j++)
		    if(a[i][j]<='Z')
		       a[i][j]=(char)((int)(a[i][j])+32);
	}
	for(int i=1;i<=m;i++){
	    cin>>b[i];
	    for(int j=0;j<b[i].size();j++)
		    if(b[i][j]<='Z')
		       b[i][j]=(char)((int)(b[i][j])+32);
	}
	//因為不分大小寫，是以把字元都轉換成小寫（，或大寫）
	for(int i=1;i<=n;i++){
		Gun=0;
	    for(int j=1;j<=m;j++)
	    	for(int k=0,l=0;k<=a[i].size();k++){
	    	//l是好名字，k是奶牛名字
	    		if(a[i][k]==b[j][l])
	    		   l++;//符合題目的不連續也可以
	    		if(l>=b[j].size()){
	    	       Gun++;break;
	    	       //表示已經比對完了一個好名字，答案增加1
				}
			}
		printf("%d\n",Gun);
	}
}