Andre Andre - 3 months ago 17
C++ Question

String matching algorithm trying to correct it

I'm trying to do string matching algorithm a brute force method. but The algorithm is not working correctly, I get an out of bound index error.

here is my algorithm

int main() {

string s = "NOBODY_NOTICED_HIM";
string pattern="NOT";

int index = 0;
for (int i = 0; i < s.size();)
{
for (int j = 0; j < pattern.size();)
{
if(s[index] == pattern[j])
{
j++;
i++;
}
else
{
index = i;
j = 0;

}
}
}
cout<<index<<endl;
return 0;
}


FIXED VERSION

I fixed the out of bound exception. I don't know if the algorithm will work with different strings

int main() {

string s = "NOBODY_NOTICED_HIM";
string pattern="NOT";

int index = 0;
int i = 0;
while( i < s.size())
{
i++;
for (int j = 0; j < pattern.size();)
{
if(s[index] == pattern[j])
{
index++;
j++;

cout<<"i is " <<i << " j is "<<j <<endl;
}
else
{
index = i;

break;
}
}
}
cout<<i<<endl;
return 0;
}

vz0 vz0
Answer

Because the inner for loop has a condition to loop while j is less than pattern.size() but you are also incrementing i inside the body. When i goes out of bounds of s.size() then index also goes out of bounds and you'd get an OutOfBounds error.

The brute force method has to test the pattern with every possible subsequence. The main condition is the length, which has to be the same. All subsequence from s are:

['NOB', 'OBO', 'BOD', 'ODY', 'DY_', 'Y_N', 'NO', 'NOT', 'OTI', 'TIC', 'ICE', 'CED', 'ED', 'D_H', '_HI', 'HIM']

There are many ways to do it, you can do it char by char, or by using string operations like taking a substring. Both are nice excercises for learning.

Starting at zero in the s string you take the first three chars, compare to the pattern, and if equal you give the answer. Otherwise you move on to the char starting at one, etc.