Part I: Naive matching

The most naive way of doing substring matching is to individually check whether a pattern string P matches the substring of length m at position 0, 1, 2, ..., n-m in the document string Y. Here, m is the length of the pattern string P and n is the length of document string Y. In other words, we are going to check whether P is the same as Y[0..m-1], Y[1..m], ..., Y[n-m...n-1], where Y[0..m-1] is the substring of length m starting at position 0 of Y, Y[1..m] is the substring at position 1, and so on.

As an example, suppose the pattern string is "dab", the document string is "abracadabra", then you would check whether "ada" is the same as the substring at position 0 ("abr"), at position 1 ("bra"), ... until you find a match at position 6.

This naive algorithm is slow. If the pattern string is of length m, each check takes O(m) time in the worst case. Since there are total n checks, the naive algorithm takes O(m*n) to perform the substring match. Nevetheless, naive matching is extremely simple and so let's get started on that.

Your job: Complete the function naive_substring_match in rkgrep.c file and test it

I have attached the relevant source code for the rkgrep.c file. The naive_substring_match function needs to completed for this part of the assignment. I look forward to reading your answer

Source Code:

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include "rkgrep.h"

#include "bloom.h"

#define PRIME 961748941

// calculate modulo addition, i.e. (a+b) % PRIME

long long

madd(long long a, long long b)

{

return (a + b) % PRIME;

}

// calculate modulo substraction, i.e. (a-b) % PRIME

long long

msub(long long a, long long b)

{

return (a>b)?(a-b):(a+PRIME-b);

}

// calculate modulo multiplication, i.e. (a*b) % PRIME

long long

mmul(long long a, long long b)

{

return (a*b) % PRIME;

}

/* naive_substring_match returns number of positions in the document where

* the pattern has been found. In addition, it stores the first position

* where the pattern is found in the variable pointed to by first_match_ind

*

* Both its arguments "pattern" and "doc" are null-terminated C strings.

*/

int

naive_substring_match(const char *pattern, const char *doc, int *first_match_ind)

{

/* Your code here */

return -1;

}