SHARE
TWEET

Untitled

a guest Jan 15th, 2020 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top