枚举每个分段的点，每次O(n)更新左边和右边的hash值
然后用双指针O(n)计算答案
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 #define ull unsigned long long 6 using namespace std; 7 struct HS{ 8 ull l,r; 9 }tmp[30010],hs[30010]; 10 ull base,b[202],c[301]; 11 int n,m; 12 char s[30010][203]; 13 14 bool cmp(HS a, HS b){ 15 if (a.l==b.l) return a.r<b.r; return a.l<b.l; 16 } 17 18 bool operator!=(HS a, HS b){ 19 return ((a.l!=b.l) || (a.r!=b.r)); 20 } 21 22 void pre(){ 23 if (base==2) c['0']=1,c['1']=2; 24 else{ 25 int cnt=0; 26 for (int i='A'; i<='Z'; i++) c[i]=++cnt; 27 for (int i='a'; i<='z'; i++) c[i]=++cnt; 28 for (int i='0'; i<='9'; i++) c[i]=++cnt; 29 c['_']=++cnt; c['@']=++cnt; 30 } 31 ++base; b[0]=1; 32 for (int i=1; i<=m; i++) b[i]=b[i-1]*base; 33 } 34 35 int main(){ 36 scanf("%d%d", &n, &m); cin>>base; 37 pre(); 38 for (int i=1; i<=n; i++){ 39 scanf("%s", s[i]+1); 40 for (int j=2; j<=m; j++) 41 hs[i].r=hs[i].r*base+(ull)c[s[i][j]]; 42 } 43 memcpy(tmp,hs,(n+1)*sizeof(HS)); 44 ull ans=0LL; 45 for (int i=2; i<=m+1; i++){ 46 int head=0; 47 sort(hs+1,hs+1+n,cmp); 48 for (int j=1; j<=n; j++){ 49 tmp[j].l=tmp[j].l*base+c[s[j][i-1]]; 50 tmp[j].r-=b[m-i]*c[s[j][i]]; 51 if (j==1 || hs[j]!=hs[j-1]) head=j; 52 if (j==n || hs[j]!=hs[j+1]) ans+=(ull)(j-head)*(j-head+1)/2; 53 } 54 memcpy(hs,tmp,(n+1)*sizeof(HS)); 55 } 56 cout<<ans<<endl; 57 return 0; 58 }