Блог пользователя t3rminated

Автор t3rminated, история, 8 лет назад, По-английски

I am doing this question I implemented it using rolling hash like for each position calculating the hash considering the string begins at that position and ends at one position back. But the problem coming is when i take mod with 1000000007 the hash value changes so i can't compare now between hashes as the value itself is changed so does anyone has a different idea?

here's my code —

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define MOD 1000000007
ll pw[10010];

ll pwr(ll base, ll p, ll mod){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
ll modularInverse(ll a,ll m) { return pwr(a,m-2,m); }
int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    
    pw[0] = 1;
    for(int i=1; i<=10010; i++)
        pw[i] = (pw[i-1]*31)%MOD;
    
    while(t--)
    {
        string s;
        cin >> s;
        ll cumu[10010];
        memset(cumu, 0, sizeof cumu);
        for(int j = 0; j < s.length(); j++)
        {
            if(j != 0)
                cumu[j] = (cumu[j-1] + (s[j]-'a'+1)*pw[j])%MOD;
            else
                cumu[j] = s[j]-'a'+1;
        }
        
        pair<int, int> a[s.length() + 1];
        
        for(int j = 0; j < s.length(); j++)
        {
          ll sum = cumu[s.length()-1] - ((j-1)>0?cumu[j-1]:0);
        //   cout << sum <<" ";
          if(j-1 < 0){a[j] = make_pair(sum, j);continue;}
             sum = (sum*modularInverse(pw[j],MOD))%MOD; 
            //  cout << sum <<" ";
          sum = (sum + cumu[j-1]*pw[s.length()-j])%MOD;
          a[j] = make_pair(sum, j);
        }
        sort(a, a + s.length());
        // for(int i = 0; i < s.length(); i++)
            cout << a[0].second + 1 << "\n";
    }
    return 0;
}
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится