落谷P3370字符串哈希

题目描述

如题&＃xff0c;给定N个字符串&＃xff08;第i个字符串长度为Mi&＃xff0c;字符串内包含数字、大小写字母&＃xff0c;大小写敏感&＃xff09;&＃xff0c;请求出N个字符串中共有多少个不同的字符串。

输入输出格式

输入格式&＃xff1a;

 

第一行包含一个整数N&＃xff0c;为字符串的个数。

接下来N行每行包含一个字符串&＃xff0c;为所提供的字符串。

 

输出格式&＃xff1a;

 

输出包含一行&＃xff0c;包含一个整数&＃xff0c;为不同的字符串个数。

 

输入输出样例

输入样例#1&＃xff1a; 复制

5
abc
aaaa
abc
abcc
12345

输出样例#1&＃xff1a; 复制

4

说明

时空限制&＃xff1a;1000ms,128M

数据规模&＃xff1a;

对于30%的数据&＃xff1a;N<&＃61;10&＃xff0c;Mi≈6&＃xff0c;Mmax<&＃61;15;

对于70%的数据&＃xff1a;N<&＃61;1000&＃xff0c;Mi≈100&＃xff0c;Mmax<&＃61;150

对于100%的数据&＃xff1a;N<&＃61;10000&＃xff0c;Mi≈1000&＃xff0c;Mmax<&＃61;1500

样例说明&＃xff1a;

样例中第一个字符串(abc)和第三个字符串(abc)是一样的&＃xff0c;所以所提供字符串的集合为{aaaa,abc,abcc,12345}&＃xff0c;故共计4个不同的字符串。

/*
&＃64;Author: Top_Spirit
&＃64;Language: C&＃43;&＃43;
*/
#include
using namespace std ;
typedef long long ll ;
const int Maxn &＃61; 1e4 &＃43; 10 ;
const int P &＃61; 131 ;
const int MOD &＃61; 9991 ;string s ;
vector ve[Maxn] ;int Hash (){int _Hash &＃61; 0 ;for (auto i : s){_Hash &＃61; (_Hash * P &＃43; i) % MOD ;}return _Hash ;
}bool Query(){int pos &＃61; Hash() ;for (int i &＃61; 0; i }int Add (){if (Query()) return 1;int pos &＃61; Hash() ;ve[pos].push_back(s) ;return 0 ;
}int main (){int n ;cin >> n ;int ans &＃61; 0 ;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){cin >> s ;if (!Add()) ans&＃43;&＃43; ;}cout <}