Reducing the time for rolling hash 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 &lt;= T &lt;= 100

1 &lt;= |S|, |P| &lt;= 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


My code in c++ :-

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;
using namespace std;
int main() 
{
long ind,j,test,kal;
cin&gt;&gt;test; //testcases' input//
for(ind=0;ind&lt;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&gt;&gt;s1&gt;&gt;s2;
   len1=s1.size();       //length of input string//
   len2=s2.size();       //length of pattern //
   for(j=0;j&lt;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&lt;=len1-len2;j++)    //iterate len1-len2 times since we get those many distinct or duplicate patterns//
   {
       for(kal=j;kal&lt;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&lt;&lt;s3&lt;&lt;" "&lt;&lt;j&lt;&lt;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.
Thanks for reading and any help will be a great favor .
So far, your code has some general problems that are much more urgent than performance:


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?.
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 //?)
You are not making enough use of the standard library.
There is too little space.  And the indentation is inconsistent.
The variable names are not helpful.  What is sum1?  s3?
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 &lt;iostream&gt;
#include &lt;numeric&gt;
#include &lt;string&gt;

int hash_code(const std::string&amp; 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&amp; string, const std::string&amp; pattern)
{
    const int pattern_hash = hash_code(pattern);
    for (std::size_t i = 0; i + pattern.size() &lt;= string.size(); ++i) {
        auto str = string.substr(i, pattern.size());
        if (hash_code(str) == pattern_hash)
            std::cout &lt;&lt; str &lt;&lt; " " &lt;&lt; i &lt;&lt; "\n";
    }
}

int main()
{
    int n;
    std::cin &gt;&gt; n;

    for (int i = 0; i &lt; n; ++i) {
        std::string string, pattern;
        std::cin &gt;&gt; string &gt;&gt; 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."