题意： 第一行输入一个数字n，接下来n行输入n个字符串，给定一个合并两条字符串的规则（记为str1和str2），如果着两条字符串无论以何种顺序连接（s1+s2或s2+s1)它们形成的新的字符串都一样，则说明它两能够合并，能够合并的字符串的数量加一。最后输出总的能够合并的字符串的数量。
题解： 利用哈希表来进行字符串的映射。详细逻辑见代码
叉姐代码：
#include <cstdio> #include <cstring> #include <string> #include <unordered_map> const int N = 1000000; int next[N]; char s[N + 1]; int main() { int n; while (scanf("%d", &n) == 1) { std::unordered_map<std::string, int> count; for (int _ = 0; _ < n; ++_) { scanf("%s", s); int length = strlen(s); memset(next, -1, sizeof(*next) * length); for (int i = 1; i < length; ++i) // 统计该字符串字串中一段连续的单字符有几个 { int j = i - 1; while (~j) { j = next[j]; if (s[j + 1] == s[i]) { next[i] = j + 1; break; } } } int j = length - 1; int period = length; while (~j) { j = next[j]; if (length % (length - (j + 1)) == 0) // 如果该字符串由单字符组成，直接将第一个字符后面的全部舍去 { period = length - (j + 1); break; } } s[period] = '\0'; count[s]++; } long long result = 0; for (auto &&iterator : count) // 计算结果 { int size = iterator.second; result += (size - 1LL) * size / 2; } printf("%lld\n", result); } }比赛时我的TLE代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int str[30]; int n, k, res; char s[maxn]; int main() { while (~scanf("%d", &n)) { memset(str, 0, sizeof(str)); res = 0; map<string, int> mp; int cnt = 0; for (int j = 0; j < n; j++) { memset(s, 0, sizeof(s)); scanf("%s", s); int len = strlen(s); bool flag = 0; if (len > 1) { int r = len - 1, l = 0; while (l <= r) // 判断该字符串是否由单字符组成 { if (s[r] != s[l] || s[r] != s[0] || s[l] != s[0]) { flag = 1; break; } l++; r--; } } if (flag) // 如果不是由单字符组成 { if (mp[s]) { mp[s]++; res += (mp[s] - 1); } else mp[s] = 1; } else // 该字符由单字符组成 { if (str[s[0] - 'a']) { str[s[0] - 'a']++; res += (str[s[0] - 'a'] - 1); } else str[s[0] - 'a'] = 1; } } printf("%d\n", res); } return 0; }我自己的代码在提交的时候要跑到了2s多，超时了，但是我感觉我这代码复杂度好像和叉姐的复杂度一样。。。。望大佬指点迷津
