rolling hash technique in http://www.spoj.com/problems/BEADS/

Правка en1, от t3rminated, 2017-01-17 12:52:59

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;
}
Теги rolling hashes

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский t3rminated 2017-01-17 12:52:59 1951 Initial revision (published)