思路
如果直接暴力的比较的话，不用想也知道会超时
所以考虑另一种方法，将前缀和的思想运用到hash中。用两个hash，一个从前往后记录，一个从后往前记录，然后枚举哪一位是不相同的，然后删掉这一位，将这一位之前的hash值和这一位之后的hash值相加，存在一个数组hs中，如果两个串的hs值是相等的，那么它俩就是相似的字符串。另外这个题自然溢出的hash完全能过，不用担心毒瘤
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int maxn = 30003;
typedef unsigned long long ULL;
const ULL base = 131;
const int Mod = 1e9+7;
using namespace std;
int n, l, s, Ans;
ULL hs1[maxn][233], hs2[maxn][233], hs[maxn];
char ch[maxn][233];
inline void init(int x) {
for(int i=1; i<=l; i++) {
hs1[x][i] = hs1[x][i-1] * 131 + ch[x][i];
}
for(int i=l; i>=1; i--) {
hs2[x][i] = hs2[x][i+1] * 137 + ch[x][i];
}
}
int main() {
scanf("%d%d%d", &n, &l, &s);
for(int i=1; i<=n; i++) {
scanf("%s", ch[i]+1);
init(i);
}
for(int i=1; i<=l; i++) {
for(int j=1; j<=n; j++) {
hs[j] = hs1[j][i-1]*233 + hs2[j][i+1]*211;
}
sort(hs+1, hs+1+n);
int ans = 1;
for(int j=1; j<n; j++) {
if(hs[j] == hs[j+1]) Ans += ans, ans ++;
else ans = 1;
}
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9405094.html
相关资源：数据结构—成绩单生成器
