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.


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.


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.


1 <= T <= 100
1 <= |S|, |P| <= 10⁵


aab 4
aba 5
baa 6 Explanation:

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//
   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//
   len1=s1.size();       //length of input string//
   len2=s2.size();       //length of pattern //
       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.


3 Answers 3


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.

  • \$\begingroup\$ Thanks!This is not exactly the rolling hash algorithm , it was just named like that.The code i wrote works the way i wanted , its just that the time needs to reduced. \$\endgroup\$ Aug 1, 2019 at 12:21
  • \$\begingroup\$ @Ananthhokage using a rolling hash should help with the time \$\endgroup\$
    – harold
    Aug 1, 2019 at 12:45
  • \$\begingroup\$ so i should learn rolling hash algorithm first? \$\endgroup\$ Aug 1, 2019 at 14:37
  • \$\begingroup\$ @Ananthhokage well it's really simple, it comes down to that one line of code that I wrote above.. with suitable initialization of course. In general with a hash function that also involves multiplying the hash by a constant, there may be some trickier math concepts involved (modular multiplicative inverse etc) but the code is still really simple. \$\endgroup\$
    – harold
    Aug 1, 2019 at 14:42
  • \$\begingroup\$ (The -96 is ill-conceived right from the start, just offsetting the sum by -96*len(P).) Multiplying the checksum with some constant before adding in another item is one way to get a position sensitive checksum, which would reduce the matches to just aab 4 in the example (in all likelihood: in general, there may be collisions with any fixed size summary of something unlimited in size). \$\endgroup\$
    – greybeard
    Jun 17 at 4:28

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

  • \$\begingroup\$ First of all thanks for answering here and responding to my other question on stackoverflow XD.I tried your your code (copy_pasted it prior to examining it) it still gave me timeout(should be less than 0.6 secs).I agree i need to use libraries more and figure out which ones are effective keeping in mind the time constraints.If you wanna try out the question yourself [link]practice.geeksforgeeks.org/contest-problem/… .Thanks again! \$\endgroup\$ Aug 1, 2019 at 12:18
  • 2
    \$\begingroup\$ As a standalone statement (like in a for loop) it does not really matter if you use ++i or i++. Saying that pre-increment is the "correct" one is a matter of taste. \$\endgroup\$ Aug 1, 2019 at 17:08
  • 1
    \$\begingroup\$ @danielspaniol yes I know about that but am afraid I might get downvoted even if I remotely sound confronting their opinion lol. \$\endgroup\$ Aug 4, 2019 at 18:22
  • 1
    \$\begingroup\$ @Ananthhokage No, of course not. There is absolutely no reason to downvote you for that. If you challenge my opinion, I will happily discuss with you. \$\endgroup\$
    – L. F.
    Aug 5, 2019 at 2:35
  • \$\begingroup\$ @danielspaniol For some strange reason I didn't noticed your comment, sorry for that. My take is that in theory they are indeed the same in this particular situation, but ++i does logically what we want to do here, and in general ++i is faster than i++, so sticking to ++i is probably a good idea. A discarded value i++ just look as "wrong" as *(&x) + char(1) + 2 + 0["\003"] - (short)5 + 9 in place of x + 10 to many of us (well, that's a bit exaggerated), also any decent compiler should generate equivalent code for them. \$\endgroup\$
    – L. F.
    Aug 5, 2019 at 2:48

Two more things about something like
- 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?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.