Advertisement
Guest User

Untitled

a guest
Jan 15th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define ll long long
  5. using namespace std;
  6.  
  7. int main(){
  8. IOS
  9. //freopen("output.txt","w",stdout);
  10. int n,m;
  11. cin>>n>>m;
  12.  
  13. string s[n];
  14.  
  15. for(int i=0;i<n;i++){
  16. cin>>s[i];
  17. }
  18. ll HASH[n][m+1];
  19. memset(HASH,0,sizeof HASH);
  20. ll p = 31;
  21. ll mod = 1000000009LL;
  22. ll p_pow[m+1];
  23. p_pow[1]=1;
  24. for(int i=2;i<=m;i++){
  25. p_pow[i] = (p_pow[i-1] * p)%mod;
  26. }
  27. for(int i=0;i<n;i++){
  28.  
  29. for(int j=1;j<=m;j++){
  30. ll temp = ((ll)(s[i][j-1]-'a'+1))*p_pow[j];
  31. HASH[i][j] = (HASH[i][j-1]+temp)%mod;
  32.  
  33. }
  34. }
  35. ll ans = 0;
  36. map<pair<pair<ll,ll> , char> ,ll>mp;
  37. for(int j=1;j<=m;j++){
  38. for(int i=0;i<n;i++){
  39. ll a = HASH[i][j-1]%mod;
  40. ll b = (HASH[i][m]-HASH[i][j])%mod;
  41. char cur = s[i][j-1];
  42. mp[{{a,b },cur}]++;
  43. for(char ch='a';ch<='z';ch++){
  44. if(ch!=cur){
  45. ans+=mp[{{a, b},ch}];
  46. }
  47. }
  48. }
  49. mp.clear();
  50.  
  51. }
  52. cout<<ans<<"\n";
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement