Algorithm to find substring in a string

Question

Can this be 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;
    }

Answer 1

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.

Answer 2

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

Answer 3

Besides fixing the bug, you can make the following improvements...

• I find it's more natural if the text is the first parameter and term the second one for a simple reason, you could make it an extension so then the text would go first.
• You don't need any of the helper variables, you can put them all inside the for declaration.
• Use a constant for the -1.
• Few years later and you can use local functions (C# 7) so you can put them inside the loop to encapsulate the logic and make it much easier to understand.
• Additionaly you could add an option for case sensitivity.

Example:

public static int find7(this string text, string term)
{
    const int indexOutOfRange = -1;

    for (int i = 0, j = 0, index = indexOutOfRange; i < text.Length; i++)
    {
        if (IsMatch())
        {
            if (IsFirstMatch()) index = i;
            if (IsSuccess()) return index;
            j++;
        }
        else
        {
            Backtrack();
            Reset();
        }

        bool IsMatch() => text[i] == term[j];
        bool IsSuccess() => j == term.Length - 1;
        bool IsFirstMatch() => j == 0;
        void Backtrack()
        {
            if (IsPartialMatch()) RestartAfterFirstMatch();

            bool IsPartialMatch() => index > indexOutOfRange;
            void RestartAfterFirstMatch() => i = index;
        }
        void Reset()
        {
            j = 0;
            index = indexOutOfRange;
        }
    }

    return indexOutOfRange;
}

Usage:

"foo bar baz".find7("u"); // -1
"foo bar baz".find7("b"); // 4
"foo bar baz".find7("bar"); // 4

Answer 4

As already pointed out you need to backtrack when match fails
You don't need to preemptively save the found position
I think this is much simpler approach

public static int? StringInString2(string stringToSearch, string stringToFind)
{
    int M = stringToFind.Count();
    int N = stringToSearch.Count();

    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;

        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
            if (stringToSearch[i + j] != stringToFind[j])
                break;

        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
            return i;
    }
    return null;
}