# Can this algorithm to find substring in string be further improved?

``````static int find(string term, string text)
{
int found = -1;
int termIndex = 0;

for (int textIndex = 0; textIndex < text.Length; textIndex++)
{
if (term[termIndex] == text[textIndex])
{
if (termIndex == term.Length-1)
return found;
if (termIndex == 0)
found = textIndex;
termIndex++;
}else
{
termIndex = 0;
found = -1;
}
}
return found;
}
``````
-
I don't code in C#, but is there a reason you can't use `text.indexOf(term)`? –  jackwanders Jul 12 '12 at 20:28
I believe this is know as the naive string searching algorithm and yes it can be improved. –  ChaosPandion Jul 12 '12 at 20:32
@ChaosPandion: Why is this considered naive, and i'd really appreciate suggestions for improvement. @jackwanders: I kinda want to write the algorithm that functions like `indexOf()` would use. –  W.K.S Jul 12 '12 at 20:39
@W.K.S - It is called naive because that's what it is. :) I do remember the Knuth–Morris–Pratt algorithm but not the details. –  ChaosPandion Jul 12 '12 at 20:42
Check out Boyer-Moore or Knuth-Morris-Pratt. You can find a C# implementation here. –  Groo Jul 12 '12 at 20:47

I do code in C#. I see two problems, one of which was already pointed out:

``````static int find(string term, string text)
{
int found = -1;
int termIndex = 0;

//quick check to protect the user from themselves
if(String.IsNullOrEmpty(term) || string.IsNullOrEmpty(text))
return -1;

for (int textIndex = 0; textIndex < text.Length; textIndex++)
{
if (term[termIndex] == text[textIndex])
{
//assign the index first, then return it
if (termIndex == 0)
found = textIndex;
//because we assign found to a *possible* match,
//we must be sure that we have a real match before returning
//so this is the ONLY place where we should return "found".
termIndex++;
if (termIndex >= term.Length)
return found;
}
else
{
termIndex = 0;
//If a match fails, revert to the start of the attempted match.
//the for loop will increment it to the next character
if(found >= 0)
textIndex = found;
found = -1;
}
}
//if we get here, the substring was not found in its entirety,
//regardless of the value of "found".
return -1;
}
``````

The first major fix in the `if` block makes sure that `found` has the proper index in the case of a one-character match; If the first character matches the single-character substring, we'd immediately return -1 because `found` was never initialized. However, if we do this, then we run the risk of finding a possible match at the end of the string, running out of characters, and incorrectly returning the index of the partial match. For example, `find("aaa", "aabaa")` would return index 3 when `term` doesn't actually exist, because it looked like a match until we ran out of characters. So, we must change the default return value to -1, and must only return the index of a possible match once we confirm that it really is a match, because if we run out of characters in `text` before we successfully reach the end of `term`, then `term` doesn't exist in `text`.

The second fix in the `else` block makes sure that multi-character substrings aren't overlooked in cases where one substring seems to match but then doesn't, but the substring starting on the very next character of `text` would match. For instance, `find("aabaa", "aaabaa")` would fail with your initial implementation, because after the algorithm found the first two 'a's, it would search for 'b' and not find it, discard that match, but then continue at index 3, when the substring starting at index 1 would have matched. Now, this does change the index of the counter variable in the for loop, which some might say is a no-no, but I see no problem with it; it's exactly the behavior that the algorithm should exhibit.

Finally, up at the very top, if `term` or `text` had been null, the function would have thrown a NullReferenceException. If `term` had been empty, same thing. `text` being empty would have worked (`text.Length` would be zero and so we'd never enter the loop), but it's easy with String.INOE() to check both at once.

-

I also don't code in C#, but if I'm right the following is the same in Java:

``````public static int find(final String term, final String text) {
int found = -1;
int termIndex = 0;

for (int textIndex = 0; textIndex < text.length(); textIndex++) {
if (term.charAt(termIndex) == text.charAt(textIndex)) {
if (termIndex == term.length() - 1) {
return found;
}
if (termIndex == 0) {
found = textIndex;
}
termIndex++;
} else {
termIndex = 0;
found = -1;
}
}
return found;
}
``````

Unfortunately, it does not seem to work. Here are some test cases:

``````assertEquals("#0", 3, find("de", "abcde")); // OK
assertEquals("#1", 1, find("a", "ababaa")); // fails, returns -1
assertEquals("#2", 1, find("ba", "ababaa")); // OK
assertEquals("#3", 2, find("abaa", "ababaa")); // fails, returns -1
assertEquals("#4", 2, find("abaa", "ababaacc")); // fails, returns -1
``````
-
+1 That's right, it won't work if search term is at the beginning of the text (`found` is initialized after the `return`), or if the text contains a prefix of the term which overlaps the actual solution (because OP's code will skip the entire prefix each time). –  Groo Jul 13 '12 at 7:59