Rolling Hash - Solution

Problem : Rolling Hash

You are given a string S and a Pattern P. You need to find all matches of hash of P in string S. Also, print the index (0 based) at which the pattern’s hash is found. If no match is found, print -1.

Hint

The hash of pattern P is calculated by summing the values of characters as they appear in the alphabets table. For reference, a is 1, b is 2, …z is 26. Now, using the mentioned values, hash of ab is 1+2=3.
Rolling Hash Contest Problem

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains two lines of input. The first line contains the string S. The second line contains the pattern P.

Output:
For each testcase, in a new line, print the matches and index separated by a space. All the matches should be printed in their own separate lines.

Constraints:
1 <= T <= 100
1 <= |S|, |P| <= 105

Examples:
Input:
1
bacdaabaa
aab
Output:
aab 4
aba 5
baa 6

Explanation:
Testcase1: P is aab, and S is bacdaabaa
Now, the hash of P: aab is 1+1+2=4
In the string S, the hash value of 4 is obtained by the following:
aab=1+1+2=4, at index 4
aba=1+2+1=4, at index 5
baa=2+1+1=4, at index 6

Solution:

#include <bits/stdc++. h>

using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        
        string pattern;
        cin>>pattern;
        
        if(pattern.length()>s.length())
        {
            cout<<"-1"<<endl;
        }
        else
        
        {
            bool flag=false;
            int hash=0;
            for(int i=0;i<pattern.length();i++)
            {
                hash=hash+((int)(pattern[i]-'a'))+1;
                
            }
            
            int current_hash=0;
            for(int i=0;i<pattern.length();i++)
            {
                current_hash=current_hash+((int)(s[i]-'a'))+1;
            }
            
            
            
            if(current_hash==hash)
            {
                cout<<s.substr(0,pattern.length())<<" "<<0<<endl;
                flag=true;
            }
            
            for(int i=1;i+pattern.length()-1<s.length()&&i<s.length();i++)
            {
                
                current_hash=current_hash+((int)(s[i+pattern.length()-1]-'a'))+1-((int)(s[i-1]-'a')+1);
                
                if(current_hash==hash)
                {
                    cout<<s.substr(i,pattern.length())<<" "<<i<<endl;
                    flag=true;
                }
                
            }
            
            if(flag==false)
            cout<<-1<<endl;
        }
    }
    return 0;
}