Question

In a text of length 1000 with the following pattern 1234123412341234... How many successful comparisons and how many unsuccessful comparisons are made by the brute-force string-matching algorithm to search for all occurrences of 341? We are looking for two answers here. (A successful comparison is when one character from the pattern matches one character from the text, otherwise it is unsuccessful.)

Answer 1

Here pattern is:1234

Text lenght is:1000

Therefore,in the text 1234 repeated 250 times(i.e total text length/pattern length=1000/4)

searching string is:341

successful comparisons=249(i.e the string 341 present 249 times in in the given pattern of 1234.....)

unsuccessful comparisons=3(i.e

1.1 comapre with 3 false

2.2 compare with 3 flase

3.finally at end 3 and 4 characters compares successfully but 1 is not present)

#include <stdio.h>
#include <string.h>
char str[100], sub[100]="341";
int count = 0, count1 = 0;
void main()
{
    int i, j, l, l1, l2,k,m,n;
    for(k=0;k<250;k++)
    {
        strcat(str,"1234");
    }  
    printf("%s\n",str);
    l1 = strlen(str);
    l2 = strlen(sub);
    for (i = 0; i < l1;)
    {
        j = 0;
        count = 0;
        while ((str[i] == sub[j]))
        {
            count++;
            i++;
            j++;
        }
        if (count == l2)
        {
            count1++;                                 
            count = 0;
        }
        else            i++;
    }  
    printf("successful comparisons are:%d\n",count1);
}