我是枚举删除的位置(设为mid),然后用 1 - mid-1的位置的hash值去乘mid+1 - l 的hash值来统计删除某一位之后的hash值,但是这样只有30分,改成题解中的方式后就A了,求解为什么
下面是代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ull unsigned long long
using namespace std;
const int M = 205;
const int N = 30005;
const ull base = 233;
int n , l , s , ans;
char c[N][M];
ull hs[N][M] , p[N] , num[N];
ull cal_kid ( int mid , int sign ) {
int hash_left = 0 , hash_right = 0;
if ( mid == 1 ) // l = 2 r = l l-1 = 1
return hs[sign][l] - hs[sign][1] * p[l - 2 + 1];
if ( mid == l ) // l = 1 r = l-1 l-1 = 0
return hs[sign][l - 1] - hs[sign][0] * p[l - 2 + 1];
hash_left = hs[sign][mid - 1] - hs[sign][0] * p[mid - 2 + 1];
hash_right = hs[sign][l] - hs[sign][mid] * p[l - mid + 1 - 1];
return hash_left * hash_right;
}
int main ( void ) {
scanf ( "%d%d%d" , &n , &l , &s );
p[0] = 1;
for ( int i = 1 ; i <= l ; i++ )
p[i] = p[i - 1] * base;
for ( int i = 1 ; i <= n ; i++ ) {
scanf ( "%s" , c[i] + 1 );
for ( int j = 1 ; j <= l ; j++ )
hs[i][j] = hs[i][j - 1] * base + c[i][j];
}
for ( int mid = 1 ; mid <= l ; mid++ ) {
memset ( num , 0 , sizeof ( num ) );
int hc = 1;
for ( int j = 1 ; j <= n ; j++ )
num[j] = cal_kid ( mid , j );
sort ( num + 1 , num + 1 + n );
for ( int j = 1 ; j <= n ; j++ )
if ( num[j] == num[j + 1] )
hc++;
else {
ans += hc * ( hc -1 ) / 2;
hc = 1;
}
ans += hc * ( hc - 1 ) / 2;
}
printf ( "%d\n" , ans );
return 0;
}