Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #define ll long long
- using namespace std;
- int main(){
- IOS
- //freopen("output.txt","w",stdout);
- int n,m;
- cin>>n>>m;
- string s[n];
- for(int i=0;i<n;i++){
- cin>>s[i];
- }
- ll HASH[n][m+1];
- memset(HASH,0,sizeof HASH);
- ll p = 31;
- ll mod = 1000000009LL;
- ll p_pow[m+1];
- p_pow[1]=1;
- for(int i=2;i<=m;i++){
- p_pow[i] = (p_pow[i-1] * p)%mod;
- }
- for(int i=0;i<n;i++){
- for(int j=1;j<=m;j++){
- ll temp = ((ll)(s[i][j-1]-'a'+1))*p_pow[j];
- HASH[i][j] = (HASH[i][j-1]+temp)%mod;
- }
- }
- ll ans = 0;
- map<pair<pair<ll,ll> , char> ,ll>mp;
- for(int j=1;j<=m;j++){
- for(int i=0;i<n;i++){
- ll a = HASH[i][j-1]%mod;
- ll b = (HASH[i][m]-HASH[i][j])%mod;
- char cur = s[i][j-1];
- mp[{{a,b },cur}]++;
- for(char ch='a';ch<='z';ch++){
- if(ch!=cur){
- ans+=mp[{{a, b},ch}];
- }
- }
- }
- mp.clear();
- }
- cout<<ans<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement