1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #include <map> #define INF 2000000000 #define P 390791ull #define P_ 323591ull using namespace std; typedef unsigned long long ll; int n,L,S,ans=0,cnt[11179120]={0}; ll hsh[11179120]={0},ppow1[306],ppow2[306],H[30005],T[30005]; bool vis[11179120]={0}; char Str[30005][205]; ll (char *s){ ll resa=0,resb=0; for(int i=0;i<L;i++) resa=P*resa+s[i],resb=P_*resb+s[i]; resa+=resb; return resa; } int read(){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } void init(){ n=read(),L=read(),S=read(); ppow1[0]=ppow2[0]=1; for(int i=1;i<=L;i++) ppow1[i]=ppow1[i-1]*P,ppow2[i]=ppow2[i-1]*P_; } void solve(){ int tmp; ll valu; for(int i=1;i<=n;i++) scanf("%s",Str[i]), H[i]=Hash(Str[i]); for(int j=0;j<L;j++){ for(int i=1;i<=n;i++){ valu=H[i],valu-=Str[i][j]*ppow1[L-j-1], valu-=Str[i][j]*ppow2[L-j-1]; T[i]=valu; } sort(T+1,T+n+1); int cur=1; for(int i=2;i<=n;i++){ if(T[i]==T[i-1])ans+=cur,cur++; else cur=1; } } printf("%dn",ans); } int main(){ init(); solve(); return 0; }
|
近期评论