Advertisement
Saleh127

UVA 353 / Hashing

Jan 22nd, 2022
886
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-23-11.20.10
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll mod[2]= {1000007707,1000007909};
  13. ll base[2]= {149,307};
  14. ll hash1[2][1000007];
  15. ll hash2[2][1000007];
  16. ll p1[1000007];
  17. ll p2[1000007];
  18.  
  19. void pwr()
  20. {
  21.     p1[0]=p2[0]=1;
  22.     for(ll i=1; i<=10005; i++)
  23.     {
  24.         p1[i]=(p1[i-1]*base[0])%mod[0];
  25.         //p2[i]=(p2[i-1]*base[1])%mod[1];
  26.     }
  27. }
  28.  
  29. void hashingg(string a,string b)
  30. {
  31.     ///for string a
  32.  
  33.     hash1[0][0]=hash1[1][0]=0;
  34.  
  35.     for(ll i=1; i<=a.size(); i++)
  36.     {
  37.         hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
  38.         //hash1[1][i]=(hash1[1][i-1]*base[1] + a[i-1])%mod[1];
  39.     }
  40.  
  41.     ///for string b
  42.  
  43.     hash2[0][0]=hash2[1][0]=0;
  44.  
  45.     for(ll i=b.size(); i>=1; i--)
  46.     {
  47.         hash2[0][i]=(hash2[0][i+1]*base[0] + b[i-1])%mod[0];
  48.         //hash2[1][i]=(hash2[1][i+1]*base[1] + b[i-1])%mod[1];
  49.     }
  50.  
  51. }
  52.  
  53. ll forwardhash(ll l,ll r)
  54. {
  55.     ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  56.  
  57.     if(x<0) x+=mod[0];
  58.  
  59.     return x;
  60. }
  61.  
  62. ll backwardhash(ll l,ll r)
  63. {
  64.     ll x=(hash2[0][l] - hash2[0][r+1]*p1[r-l+1])%mod[0];
  65.  
  66.     if(x<0) x+=mod[0];
  67.  
  68.     return x;
  69. }
  70.  
  71. int main()
  72. {
  73.    ios_base::sync_with_stdio(0);
  74.    cin.tie(0);cout.tie(0);
  75.  
  76.    pwr();
  77.  
  78.    string a;
  79.  
  80.    while(cin>>a)
  81.    {
  82.         string b;
  83.  
  84.         ll i,j,k,l=0,n,m=0;
  85.  
  86.         b=a;
  87.  
  88.         hashingg(a,b);
  89.  
  90.         map<pair<ll,ll>,ll>xx;
  91.  
  92.         set<char>y;
  93.  
  94.         for(i=0;a[i];i++)
  95.         {
  96.              y.insert(a[i]);
  97.         }
  98.  
  99.         l=a.size();
  100.  
  101.         m=y.size();
  102.  
  103.         for(i=2;i<=l;i++)
  104.         {
  105.              for(j=1;j<=l-i+1;j++)
  106.              {
  107.                   ll fr=forwardhash(j,j+i-1);
  108.                   ll bc=backwardhash(j,j+i-1);
  109.  
  110.                   if(fr==bc)
  111.                   {
  112.                        if(xx[{fr,bc}]==0) m++;
  113.                        xx[{fr,bc}]=1;
  114.                   }
  115.              }
  116.         }
  117.  
  118.         cout<<"The string '"<<a<<"' contains "<<m<<" palindromes."<<endl;
  119.  
  120.    }
  121.  
  122.  
  123.    get_lost_idiot;
  124. }
  125.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement