Task was to write a function to find substring in a given string.
Answer:
One possible O(n2) solution from Wikipedia:
Edited by moderator
Answer:
One possible O(n2) solution from Wikipedia:
int NaiveSearch(string s[1..n], string sub[1..m])
{
for i from 1 to n-m+1
{
for j from 1 to m
{
if (s[i+j-1] != sub[j]) break;
return i;
}
}
return -1;
}
Edited by moderator
Wikipedia link:
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm