Implementing StrStr()

Question

This is a naive implementation - I know that there are algorithms like KMP

However I was trying to implement it as best as I can.

string test = "giladdarmonwhatareyoudoing";
int index = StrStr(test, "are");
//Returns an index to the first occurrence of str2 in str1,
//or a -1 pointer if str2 is not part of str1.
public int StrStr(string test, string strToFind)
{
 for (int i = 0; i < test.Length; i++)
 {
 if (test[i] == strToFind[0])
 {
 int j;
 for (j = 0; j < strToFind.Length; j++)
 {
 if (test[i + j] != strToFind[j])
 {
 break;
 }
 }
 if (j == strToFind.Length)
 {
 return i;
 }
 }
 }
 return -1;
}

Answer 1

Algorithm

• your implementation has some serious bugs and unexpected behaviour.

  • If passing String.Empty as second parameter, it throws an IndexOutOfRangeException

  • If passing the unique ending part of the first parameter appended by at least one character to the second parameter, it throws an IndexOutOfRangeException

    string test = "giladdarmonwhatareyoudoing";
    int index = StrStr(test, "ng1"); 
    

  • If you are passing null as either first or second parameter a NullReferenceException is thrown. Here it would be better to throw an ArgumentNullException by using a guard clause.

    if (test == null) { throw new ArgumentNullException("test"); }
    if (strToFind == null) { throw new ArgumentNullException("strToFind"); } 
    

• your implementation could be improved by

  • checking if strToFind.Length > test.Length
  • checking if test.Length - i > strToFind.Length

Naming

You shouldn't use hungarian notation. Consider to rename strToFind to searchForm or searchArgument.

Refactoring

After extracting the inner loop to a separate method, removing the now unneeded if (test[i] == strToFind[0]) and implementing the above we will get

public int StrStr(string value, string searchArgument)
{
 if (value == null) { throw new ArgumentNullException("value"); }
 if (searchArgument == null) { throw new ArgumentNullException("searchArgument"); }
 if (searchArgument.Length == 0) { return 0; }
 int searchLength = searchArgument.Length;
 int length = value.Length;
 if (searchLength > length) { return -1; }
 for (int i = 0; i < length; i++)
 {
 if (length - i < searchLength) { return -1; }
 if (IsMatchAtIndex(value, searchArgument, i)) { return i; }
 }
 return -1;
}
private bool IsMatchAtIndex(String value, String searchArgument, int startIndex)
{
 for (int j = 0; j < searchArgument.Length; j++)
 {
 if (value[startIndex + j] != searchArgument[j])
 {
 return false;
 }
 }
 return true;
} 

I prefer the above, but you could also add

if (length - i < searchLength) { return -1; } 

inverted as condition to the for loop like

for (int i = 0; i < length && length - i >= searchLength; i++)
{
 if (IsMatchAtIndex(value, searchArgument, i)) { return i; }
}

• Gilad: I used string.IsNullOrEmpty(test) in the end for user Input great thing to remember to do for next time thanks.

Answer 2

//Returns an index to the first occurrence of str2 in str1,
//or a -1 pointer if str2 is not part of str1.
public int StrStr(string test, string strToFind)

That comment would be much better off as an XML comment, so that client code can see the documentation for the method with IntelliSense:

/// <summary>
/// Returns an index to the first occurrence of str2 in str1,
/// or a -1 pointer if str2 is not part of str1.
/// </summary>
public int StrStr(string test, string strToFind)

Another problem, is that the str1 and str2 parameters mentioned in the comment, aren't the actual parameter names you're using. You can use paramref for that:

/// <summary>
/// Finds the index of the first occurrence of <paramref name="test"/> in <paramref name="strToFind"/>.
/// </summary>
/// <param name="test">The input string.</param>
/// <param name="strToFind">The value to find.</param>
/// <returns>Returns -1 if specified value is not found.</returns>
public int StrStr(string test, string strToFind)

MSDN:

The <paramref> tag gives you a way to indicate that a word in the code comments, for example in a <summary> or <remarks> block refers to a parameter. The XML file can be processed to format this word in some distinct way, such as with a bold or italic font.

Use the <returns> XML tag to specify a function's return value - the <summary> tag should simply state what the function does, not cover all possible outcomes.

Answer 3

Mostly minor stuff:

1. You have probably taken the name from the C function but StrStr is actually not really a good name. StartIndexOf or similar might be better.

2. You could write it as an extensions method to string which would result in a nicer calling syntax. It would look like this then:

   public static int StartIndexOf(this string test, string toFind)
   {
    ....
   }
   

   and call it like this:

   string test = "giladdarmonwhatareyoudoing";
   int index = test.StartIndexOf("are");