Part I: Naive matching The most naive way of doing substring matching is to indi
ID: 3723147 • Letter: P
Question
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 <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <getopt.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#include <ctype.h>
#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;
}
Explanation / Answer
//Function naive_substring_match()
//Please upvote, if you like the answer.
//If you have any doubt with the code feel free to ask in comments, we are here for you.
int naive_substring_match(const char *pattern, const char *doc, int *first_match_ind)
{
/* Your code here */
/*
patt_len: length of pattern
doc_len: length of doc
ctr: number of times pattern was found
*/
int i,j,patt_len,doc_len,ctr=0;
for(i=0;pattern[i]!='';i++);
patt_len=i;
for(i=0;doc[i]!='';i++);
doc_len=i;
if(patt_len<=doc_len)
{
for(i=0;i<=(doc_len-patt_len);i++)
{
j=0;
while((pattern[j]==doc[i])&&(j<patt_len))
j++;
if((j==patt_len)//if pattern was same throughout substring
{
if(ctr==0) //if pattern was found for the first time
*first_match_ind=i;
ctr++;
}
}
}
return ctr;
}