3
\$\begingroup\$

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;
    }
\$\endgroup\$
7
  • 3
    \$\begingroup\$ I don't code in C#, but is there a reason you can't use text.indexOf(term)? \$\endgroup\$ – jackwanders Jul 12 '12 at 20:28
  • \$\begingroup\$ I believe this is know as the naive string searching algorithm and yes it can be improved. \$\endgroup\$ – ChaosPandion Jul 12 '12 at 20:32
  • \$\begingroup\$ @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. \$\endgroup\$ – W.K.S Jul 12 '12 at 20:39
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – ChaosPandion Jul 12 '12 at 20:42
  • 2
    \$\begingroup\$ Check out Boyer-Moore or Knuth-Morris-Pratt. You can find a C# implementation here. \$\endgroup\$ – Groo Jul 12 '12 at 20:47
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ +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). \$\endgroup\$ – Groo Jul 13 '12 at 7:59
2
\$\begingroup\$

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Are you sure this backtracks? Please try "aabaa", "aaabaa" \$\endgroup\$ – paparazzo Feb 19 '17 at 21:06
  • 1
    \$\begingroup\$ @Paparazzi, admittedly, I didn't think of that, I'll need to take a look. thx. \$\endgroup\$ – t3chb0t Feb 19 '17 at 21:07
  • 1
    \$\begingroup\$ @Paparazzi I think I got it right this time. \$\endgroup\$ – t3chb0t Feb 19 '17 at 21:25
  • 1
    \$\begingroup\$ I like the way my code goes about it better \$\endgroup\$ – paparazzo Feb 19 '17 at 21:27
  • 1
    \$\begingroup\$ @Paparazzi maybe, but unfortunatelly it's quite hard to read and understand (so are the other solutions) and I couldn't understand it without actually debugging it (reading the lengthy comments), that's why I love the new local functions, they make it super easy to write comprehensible code. Anyway, thx for your comment, it was a nice exercise ;-) \$\endgroup\$ – t3chb0t Feb 19 '17 at 21:35
1
\$\begingroup\$

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;
}
\$\endgroup\$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.