5
\$\begingroup\$

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| <= 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 <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. Thanks for reading and any help will be a great favor .

\$\endgroup\$
10
\$\begingroup\$

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

\$\endgroup\$
  • \$\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\$ – Ananthhokage Aug 1 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\$ – danielspaniol Aug 1 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\$ – Ananthhokage Aug 4 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 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 at 2:48
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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\$ – Ananthhokage Aug 1 at 12:21
  • \$\begingroup\$ @Ananthhokage using a rolling hash should help with the time \$\endgroup\$ – harold Aug 1 at 12:45
  • \$\begingroup\$ so i should learn rolling hash algorithm first? \$\endgroup\$ – Ananthhokage Aug 1 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 at 14:42

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.