[Solved] Rolling Hash Contest Problem

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.

Note: All the matches should have same length as pattern P.

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| <= 10⁵

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 <iostream>
#include <cmath>
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;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
    
    public static void rollHash(String s, String pattern) {
        if(pattern.length() > s.length()) {
	        System.out.println(-1);
	    } else {
	        boolean flag = false;
    	    int hash = 0;
    	    for(int i=0; i<pattern.length(); i++) {
    	        hash+=((int)pattern.charAt(i) - 'a') + 1;
    	    }
    	    
    	    int current_hash=0;
    	    for(int i=0; i<pattern.length(); i++) {
    	        current_hash+=((int)s.charAt(i) - 'a') + 1;
    	    }
    	    if(current_hash==hash) {
    	        System.out.println(s.substring(0, pattern.length()) + " "+0);
    	        flag = true;
    	    }
    	    
    	    for(int i=1; i+pattern.length()-1 < s.length() && i<s.length(); i++) {
    	        current_hash+=((int)s.charAt(i+pattern.length()-1) - 97) + 1 - ((int)s.charAt(i-1) - 97 +1);
    	        if(current_hash==hash) {
    	            System.out.println(s.substring(i, i+pattern.length()) + " " + i);
    	            flag = true;
    	        }
    	    }
    	    if(flag==false){
    	        System.out.println(-1);
    	    }
	    }
    }
    
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine().trim());
		while(t-->0){
		    String str = br.readLine().trim();
		    String pattern = br.readLine().trim();
		    rollHash(str, pattern);
		}
	}
}

import atexit
import io
import sys

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        s=str(input())
        p=str(input())

        score = 0
        for char in p:
            score+=ord(char)-ord('a')+1

        a=[]
        for char in s:
            a.append(ord(char)-ord('a')+1)

        sub_arrays= []
        window_start = 0
        window_end = 0
        curr_sum = a[0]

        while(window_start<len(s) and window_end<len(s)):
            if curr_sum<score:
                window_end += 1
                if window_end == len(s):
                    break
                curr_sum+=a[window_end]


            elif curr_sum>score:
                while(window_start<=window_end and curr_sum>score):
                    curr_sum-=a[window_start]
                    window_start+=1

                if curr_sum>score:
                    assert(window_start==window_end)
                    while(window_end<len(s) and a[window_start]>score):
                        window_start+=1
                        window_end+=1
            else:
                # check for size of subarray.. should be equal to size of p
                if window_end-window_start+1==len(p):
                    sub_arrays.append([window_start,window_end])
                curr_sum -= a[window_start]
                window_start+=1

        for sub_arr in sub_arrays :
            print(s[sub_arr[0]:sub_arr[1]+1],sub_arr[0])
            
        if len(sub_arrays)==0:
            print(-1)

Happy Learning – If you require any further information, feel free to contact me.