Write a function implementing rabin karp algorithm correctly

Question

0.00/5 (No votes)

See more:

I am assigned to write a function that implements the Rabin Karp algorithm with a single text and an array list of possible patterns. The pattern is an array of k pointers and the length of the text is m. The result did not pass the test function provided. I can't figure out the error. Can someone tell me where the errors are or how can I write a different test function to see what I am returning here so I can compare it to the correct one?

What I have tried:

C++

  int substring(char * text, int k, int m, char* patterns[])
{   
    int hp = 0; // hash value of pattern
    int t = 0; // hash value of text
    int h = 0; 
    int i , j;
    int p = 1009; //prime number > 1000
    int d = 256; // random base of polynomial
    text[200];
    char pat[100];

    for (i = 0; i < k - 1; i++)
        h = (h*d) % p;

    //hash value of pattern and hash value of the compared text substring
    for (i = 0; i < k; i++)
    {
        hp = (d*p + pat[i]) % p;
        t = (d*p + text[i]) % p;
    }

    //slide pattern over text
    for (i = 0; i <= m - k; i++)
    {
        if (hp == t)
        {
            for (j = 0; j < k; j++)
            {
                if (text[i+j] != patterns[j])
                    break;
            }
            if (j == k)
                return i;
        }

        if (i < m - k)
        {
            t = (d*(t - text[i] * h) + text[i+k]) % p;

            if (t < 0)
                t = (t + p);
        }
    }

}

Posted 11-Dec-16 4:32am

Member 12898564

Updated 11-Dec-16 6:29am

Add a Solution

Comments

[no name] 11-Dec-16 11:26am

In addition to Solution 1, don't get into the habit of using one character variable names. You might remember what 'h' was used for today but next week you won't. If 'p' is a prime number then make the variable name primeNumber and you won't have to try and remember what it is and you won't have to have an additional comment to remind you what it is.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2016-12-11T04:52:00

No, that is part of the assignment: getting it to work!
Use the debugger, and start looking at what is happening while the code is running.
I can't be explicit - I have no idea which system you are using, so I can't tell you what the debugger commands are, but Google will tell you if you ask - put a breakpoint at the start of the function, and the debugger will stop when it reaches it. You can then look at variable contents, and single step lines to see what effect they have and where flow goes.
Try to work out before you execute each line what you expect to happen and compare that to what did happen. If the two don't match, why not?

Give it a try: you wrote the code so you know what you expect it to do - the fun part is getting it to do exactly what you wanted! :D

Patrice T · Answer 2 · 2016-12-11T06:29:00

Quote:
The result did not pass the test function provided. I can't figure out the error.

This is your code, you should know how it work, with the debugger, see it doing its stuff and check that it match your expectations.

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

Write a function implementing rabin karp algorithm correctly

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us