题意：

判定有多少对字符串只有一个字母不同。字符串个数≤30000，长度≤300。

题解：

求出第i个字符串前j个字符的哈希值hs[i][j]，然后枚举去掉所有字符串的第几位，将去掉后的字符串的哈希值用hs数组直接算出，排序后检查有没有相同的计入答案。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 30010 6 #define hash 2333 7 #define ll unsigned long long 8 using namespace std; 9 10 ll hs[maxn][210],tmp[maxn],power[maxn],ans; int n,k,s; char str[210];11 int main(){12     scanf("%d%d%d",&n,&k,&s); power[0]=1; inc(i,1,k)power[i]=power[i-1]*hash;13     inc(i,1,n){14         scanf("%s",str+1); inc(j,1,k)hs[i][j]=hs[i][j-1]*hash+str[j];15     }16     inc(i,1,k){17         inc(j,1,n)tmp[j]=hs[j][k]-hs[j][i]*power[k-i]+hs[j][i-1]*power[k-i+1];18         sort(tmp+1,tmp+1+n); int cnt=1;19         inc(j,2,n)if(tmp[j]==tmp[j-1])ans+=cnt,cnt++;else cnt=1;20     }21     printf("%llu",ans); return 0;22 }
       
      
     

 

20160820