Thread: string searching algorithm......help

What are you searching for, a substring or chars? That makes all the difference. If searching for chars, all you have to do is go through the array of chars checking it.

Try to implement first the simpliest method.
Boyer-Moore can wait, and you don't need such advanced techniques until you're searching in huge files.

The algorythm is this simple:

Search for the first character of your string in the target.
if found, check whether second character from the search string matches the second character from target string, and so on, for th é whole length of the searched string. If all chars match, you're done, return strings index from the tartget. Else, continue the search. You can even modify the algorythm to find all occurences of the given string if needed.

// note: this is just a draft version I typed in here quickly
// might not compile ;°), just to give you an idea

long simpleSearch( &searchString, &target )
{
bool matchFlag = false;
while(1) do
{
if ( searchString[0] == target[y] )
{
matchFlag = true;
for (int k = 1; k < strlen(searchString); k++ )
{
if ( searchString[k] != target[y+k] )
{
matchFlag = false;
break;
} // if
} // for
if ( matchFlag ) break;
}

y++;
if ( y > len( target[] ) ) // target string exceeded?
{
matchFlag = false;
break;
}
} // while

if ( matchFlag ) // if found,
return (y) // return starting index

else
return -1; // return -1 if none found
}

Yup that's the idea. When searching, you can look for the substring like that. Although in large files, that can be quite time comsuming. But, start out with that. It's good.