题目描述

《相同的字符串》

【相同的字符串】字符串哈希 给定 N (N<=10000) 个字符串，每个字符串的长度<=1500，字符串包含数字和大小写字母。如果存在完全相同的字符串，则输出“yes”，否则输出“no”。 【输入样例】 5 12aB 12ab 123b 12ab fdfd 【输出样例】 yes #include #include using namespace std; #define base 261 #define P 1007 // 字符串哈希函数 int hashID(string s){ int hash = 0; // 哈希值（地址） // 迭代运算哈希值 for (int i = 0; i < s.length(); i++) hash = ((long long)hash * base + s[i]) % P; return hash; } // 哈希表保存字符串 vector table[P+2]; // 表的尺寸要比P大 int main() { int N; string s; cin >> N; for(int i=1;i<=N;i++){ cin >> s; int index = hashID(s);// 计算哈希地址（数组下标） // 先查看 s 是否已经存在，是，则说明出现重复 for(int j=0;j < table[index].size();j++){ if(table[index][j] == s){ cout << "yes" << endl; return 0; } } table[index].push_back(s); // 不重复的，直接放入 } // 都不重复 cout << "no" << endl; return 0; }

输入格式

无

输出格式

（见样例）

样例

输入样例 1

5
12aB
12ab
123b
12ab
fdfd

输出样例 1

yes