YEZAELP

SMMR-Chi-007: Anagram Substring

Dec 5th, 2021
576
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli BP = 98765431;
  6. const int N = 1e2 + 10;
  7. char str[N + 10];
  8. lli pw[27];
  9. int len;
  10.  
  11. int to_int(char a){
  12.     return a - 'a' + 1;
  13. }
  14.  
  15. int CountString(int l){
  16.     lli hsh = 0;
  17.     for(int i=1;i<=l-1;i++)
  18.         hsh += pw[ to_int(str[i]) ];
  19.     lli cnt = 0;
  20.     map <lli, int> keep;
  21.     for(int i=l;i<=len;i++){
  22.         hsh += pw[ to_int(str[i]) ];
  23.         cnt += keep[hsh];
  24.         keep[hsh] ++;
  25.         hsh -= pw[ to_int(str[i - l + 1]) ];
  26.     }
  27.     return cnt;
  28. }
  29.  
  30. int main(){
  31.  
  32.     scanf("%s", str + 1);
  33.     len = strlen(str + 1);
  34.  
  35.     pw[0] = 1;
  36.     for(int i=1;i<=26;i++){
  37.         pw[i] = pw[i - 1] * BP * i;
  38.     }
  39.  
  40.     int ans = 0;
  41.     for(int l=1;l<=len;l++){
  42.         ans += CountString(l);
  43.     }
  44.  
  45.     printf("%d", ans);
  46.  
  47.     return 0;
  48. }
RAW Paste Data