Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Description
Problem A
Concatenation of Languages
Input File: Standard Input
Output: Standard Output
A language is a set of strings. And the concatenation of two languages is the set of all strings that are formed by concatenating the strings of the second language at the end of the strings of the first language.
For example, if we have two language A and B such that:
A = {cat, dog, mouse}
B = {rat, bat}
The concatenation of A and B would be:
C = {catrat, catbat, dograt, dogbat, mouserat, mousebat}
Given two languages your task is only to count the number of strings in the concatenation of the two languages.
Input
There can be multiple test cases. The first line of the input file contains the number of test cases, T(1≤T≤25). Then T test cases follow. The first line of each test case contains two integers, M and N(M,N<1500),
the number of strings in each of the languages. Then the next M lines contain the strings of the first language. The N following lines give you the strings of the second language. You can assume that the strings are formed
by lower case letters (‘a’ to ‘z’) only, that they are less than 10 characters long and that each string is presented in one line without any leading or trailing spaces. The strings in the input languages
may not be sorted and there will be no duplicate string.
Output
For each of the test cases you need to print one line of output. The output for each test case starts with the serial number of the test case, followed by the number of strings in the concatenation of the second language after the first language.
Sample Input Output for Sample Input
|
2 3 2 cat dog mouse rat bat 1 1 abc cab |
Case 1: 6 Case 2: 1
|
Problem setter: Monirul Hasan
Special Thanks: Shahriar Manzoor
解题思路：
这道题作为第二道字符串hash题，第一道还是昨晚上的CF的D题，，皮球教给我的，，就是用字符串hash做的，当时我还准备O（n2）暴力枚举，那样必定会T，，，
然后呢，今天起来，在VJ上开了个字符串hash专题，这几天下决心切完。。。
就是字符串的技巧有些问题，再没什么问题了，就是把先前有的放进map里，map<string,int>Map，这个STL，然后扫一遍，hash判重了。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
# include<cstring>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<set>
# include<map>
using namespace std;
# define inf 999999999
# define MAX 1500+4
char A[MAX][14];
char B[MAX][14];
char temp[14<<1];
map<string,int>Map;
int n,m;
void init()
{
Map.clear();
}
void input()
{
cin>>m>>n;
getchar();
for ( int i = 0;i < m;i++ )
{
gets(A[i]);
}
for ( int i = 0;i < n;i++ )
{
gets(B[i]);
}
}
void solve()
{
for ( int i = 0;i < m;i++ )
{
for ( int j = 0;j < n;j++ )
{
strcpy( temp,A[i] );
strcat( temp,B[j] );
if ( !Map[temp] )
{
Map[temp]++;
}
}
}
}
int main(void)
{
int t;cin>>t;
int icase = 1;
while ( t-- )
{
init();
input();
solve();
printf("Case %d: ",icase++);
cout<<Map.size()<<endl;
}
return 0;
}