问题 C: 维护集合
时间限制: 1 Sec 内存限制: 512 MB
题目描述
维护一个字符串集合:初始为空,依次处理一些插入操作,并在插入 之后输出该字符串在集合中出现的次数。
输入
输入文件包含若干行,每行为一个字符串,依次代表一个待插入的字 符串。该字符串一定非空,且仅包含英文字母和数字。
输出
对于每个插入操作输出一行一个整数,代表插入该字符串之后,该字 符串在集合中出现的次数。
样例输入
str1
str2
str1
str1
str2
str3
样例输出
1
1
2
3
2
1
提示
字符串的长度不超过 100,字符串个数不超过100000。
这题很容易想到Hash,但100000的个数非常容易出现重复导致WA。C++中可以用map直接存储判断。
Code:
#include <cstdio>标签:map,代码,t2,long,t1,字符串,集合,维护,st From: https://blog.51cto.com/u_15888102/5878326
#include <iostream>
#include <cstring>
#include <map>
long long M1=313571787;
long long M2=1000000037;
std::map<std::pair<long long,long long>,int>map;
char st[1000];
int main()
{
while(scanf("%s",st+1)!=EOF){
int len=strlen(st+1);
long long t1=0;
long long t2=0;
for(int i=1;i<=len;i++){
(t1=t1*29+st[i]*41)%=M1;
(t2=t2*31+st[i]*43)%=M2;
}
map[std::make_pair(t1,t2)]++;
printf("%d\n",map[std::make_pair(t1,t2)]);
}
return 0;
}