CodingBeast23's blog

By CodingBeast23, history, 3 years ago, In English

I am getting time limit exceeded for 3 test cases. I used rolling hash for solving this. Any suggestions fot optimizing it?

Thank You.

https://cses.fi/problemset/task/2102/

My Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
class RollHash{
public:
    int Hash[1000005];
    RollHash(){
        memset(Hash,0,sizeof Hash);
    }
    void fillRoll(string s)
    {
        int n = s.length();
        int x = 131;
        for(int i=0;i<n;i++)
        {
            Hash[i+1] = (Hash[i] + x*(s[i]-'a'+1))%mod;
            x*=131;
            x%=mod;
        }
    }
    int power(int a,int b)
    {
        if(b == 0)return 1;
     
        int ans = 1;
        while(b > 0)
        {
           
            if(b%2)
                ans = (ans*a)%mod;
            a = (a*a)%mod;
     
            b/=2;
     
        }
        return ans;
    }
    int get(int l,int r)
    {
        return ((Hash[r] - Hash[l-1] + mod)*power(power(131,l-1),mod-2))%mod;
    }
};
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    string word;
    cin >> word;
    int n = word.length();
 
    RollHash r;
 
    r.fillRoll(word);
    int m;
    cin >> m;
    while(m--)
    {
        int flag = 0;
        string s;
        cin >> s;
        int hash = 0;
        int x = 131;
 
        for(int i=0;i<s.length();i++)
        {
            hash = (hash + x*(s[i]-'a'+1))%mod;
            x*=131;
            x%=mod;
        }
 
        for(int i=1;i+s.length()-1<=n;i++)
        {
            int x = i;
            int y = i + s.length() - 1;
            if(r.get(x,y) == hash)
            {
                flag = 1;
                break;
            }
        }
        if(flag)cout << "YES\n";
        else
            cout << "NO\n";
    }
 
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved this question and counting pattern question using binary search on suffix array of string.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it
Spoiler
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is stll giving TLE, is it possible for you to share your code.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use a suffix automaton rather than hashing for a deterministic solution.