枚举每个分段的点，每次O(n)更新左边和右边的hash值
然后用双指针O(n)计算答案
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #define ull unsigned long long using namespace std; struct HS{ ull l,r; }tmp[],hs[]; ull ],c[]; int n,m; ][]; bool cmp(HS a, HS b){ if (a.l==b.l) return a.r<b.r; return a.l<b.l; } bool operator!=(HS a, HS b){ return ((a.l!=b.l) || (a.r!=b.r)); } void pre(){ ) c[,c[; else{ ; for (int i='A'; i<='Z'; i++) c[i]=++cnt; for (int i='a'; i<='z'; i++) c[i]=++cnt; '; i++) c[i]=++cnt; c['_']=++cnt; c['@']=++cnt; } ++]=; ; i<=m; i++) b[i]=b[i-]*base; } int main(){ scanf("%d%d", &n, &m); cin>>base; pre(); ; i<=n; i++){ scanf(); ; j<=m; j++) hs[i].r=hs[i].r*base+(ull)c[s[i][j]]; } memcpy(tmp,hs,(n+)*sizeof(HS)); ull ans=0LL; ; i<=m+; i++){ ; sort(hs+,hs++n,cmp); ; j<=n; j++){ tmp[j].l=tmp[j].l*]]; tmp[j].r-=b[m-i]*c[s[j][i]]; || hs[j]!=hs[j-]) head=j; ]) ans+=(ull)(j-head)*(j-head+)/; } memcpy(hs,tmp,(n+)*sizeof(HS)); } cout<<ans<<endl; ; }
