Reducing the time for rolling hash

Question

I tried this problem below and solved it in O(test_cases * string_length * pattern_length) complexity involving three nested loops. I want to know how can I further decrease time. I figured as much:

1: I'm comparing few patterns more than once.

2: Should find a way to not repeat the comparisons which I am unable to do.

The problem is as below:-

We 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.

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

My code in C++ :-

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() 
{
long ind,j,test,kal;
cin>>test; //testcases' input//
for(ind=0;ind<test;ind++)
{
   long len1,len2,sum1=0,sum2=0;  
   string s1,s2,s3;  //s1 for the input string,s2 for pattern,s3 to print the patterns that we find//
   cin>>s1>>s2;
   len1=s1.size();       //length of input string//
   len2=s2.size();       //length of pattern //
   for(j=0;j<len2;j++)
   {
       sum2=sum2+(int)s2[j]-96;   //doing the hash sum of pattern first so that i need not do pattern matching//
   }
   for(j=0;j<=len1-len2;j++)    //iterate len1-len2 times since we get those many distinct or duplicate patterns//
   {
       for(kal=j;kal<j+len2;kal++)  //iterate j+len2 times which is size of the pattern each time//
       {
           sum1=sum1+(int)s1[kal]-96; //updating the sum obtained//
           s3.push_back(s1[kal]);  //since we also need to print the pattern which has the hash sum//
       }
       if(sum1==sum2)        //if the sum matches print the string and starting index//
       cout<<s3<<" "<<j<<endl;
       s3.erase();           //clear the string for next testcase//
       sum1=0;               //clear the sum for next testcase//
   }
}
return 0;}

Please suggest changes that reduces the time.

Answer 1

This code does not implement a rolling hash. For every iteration of the main loop, the hash is reset and then entirely re-calculated from nothing with an inner loop. A rolling hash would remove a character from the hash and then add a new character, doing only a constant amount of work per sub-string.

There are some edge-cases for you to work out, but main element of the technique is this:

hash = hash - s1[kal - len2] + s1[kal]

No inner loop. Also no - 96 because it is cancelled out.

Answer 2

So far, your code has some general problems that are much more urgent than performance:

1. You are using namespace std;. This is an extremely bad habit and will ruin your life ("this is a contest and I write everything in main" is not an acceptable excuse). See Why is using namespace std; considered bad practice?.

2. The main function is very long and a reader cannot tell at a glance what it does. If you need so many comments, you should consider refactoring your code. (Also, why do your comments end with //?)

3. You are not making enough use of the standard library.

4. There is too little space. And the indentation is inconsistent.

5. The variable names are not helpful. What is sum1? s3?

6. j++ is being used instead of the correct ++j. See Difference between pre-increment and post-increment in a loop?.

Also, please avoid std::endl when not necessary. Use '\n' instead. See C++: std::endl vs \n.

And str.erase() is much less intuitive than str.clear(). (In fact, I didn't know until today that erase can be invoked this way.)

Here's I would write the same code, at the very least: (30 seconds code, not tested comprehensively)

#include <iostream>
#include <numeric>
#include <string>

int hash_code(const std::string& pattern)
{
    // note: c - 'a' + 1 is not portable
    return std::accumulate(pattern.begin(), pattern.end(), 0,
                           [](int x, char c){ return x + (c - 'a' + 1); });
}

void search(const std::string& string, const std::string& pattern)
{
    const int pattern_hash = hash_code(pattern);
    for (std::size_t i = 0; i + pattern.size() <= string.size(); ++i) {
        auto str = string.substr(i, pattern.size());
        if (hash_code(str) == pattern_hash)
            std::cout << str << " " << i << "\n";
    }
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::string string, pattern;
        std::cin >> string >> pattern;
        search(string, pattern);
    }
}    

(Also, the input style is quite strange, I have to admit, but that seems to be beyond your control.)

Incidentally, I don't think you properly implemented the sentence "If no match is found, print -1."

Answer 3

Two more things about something like
sum=sum+(int)pattern[j]-96;:
- 96 is a magic number: The reader is left to figure out what it means here. ('a' - 1) is portable and suggestive.
- C has assignment operators to avoid repeating an "operand that gets assigned the result":
 sum += pattern[j] - 'a' + 1;

You don't need to collect the characters from the input string contributing to the checksum: They stay right there.

I don't see comparing patterns more than once.
For patterns of same length, checksums for parts of the input string get recomputed - if so inclined, try to exploit that.
For patterns P1 of length l1 and P2, |P2| = l2 = l1 + 1, the checksum to compare with checksum S2 of P2 is just "one computation step from S1" - but don't try to exploit this:
That way lies madness. (What if there was a P3: l3 = l1 + l2? P4:  l4 = l3 - 1?)