How to find substring from string without using indexof method in C#?

Question

I want to find the position of a substring in a string if present without using any string method including indexof. I tried so much times but failed. Will anybody tell me how to do in C#? We can use .Length operator.

Solution 1

Sorry.. thought this would be a fun exercise for me, so...

Spoiler

class Program
{
    static void Main(string[] args)
    {
        string str = "abcdefg";
        string substr = "cde";
        int index = IndexOf(str, substr);
        Console.WriteLine(index);
        Console.ReadLine();
    }

    private static int IndexOf(string str, string substr)
    {
        bool match;

        for (int i = 0; i < str.Length - substr.Length + 1; ++i)
        {
            match = true;
            for (int j = 0; j < substr.Length; ++j)
            {
                if (str[i + j] != substr[j])
                {
                    match = false;
                    break;
                }
            }
            if (match) return i;
        }

        return -1;
    }
}

Solution 2

Assuming this is homework, my suggestion is to bear in mind that a string is an IEnumerable of chars. So you can loop through the characters in your string...

Solution 3

Since any homework that inspired the question is well past due, here's a stab at a reasonably performant answer.

Simply cycling through the larger string, and cycling through the substring comparing each character as one goes takes Θ((n-m+1) m) time where m is the length of the substring, and n the index where the smaller string is found, or if there is no match the length of the larger minus that of the smaller.

There are a few different algorithm that give better performance, which differ among themselves in terms of which cases they work best in. The Knuth-Morris-Pratt algorithm takes Θ(m) to set up and then Θ(n) time to find, because it first creates a table to know how far ahead it can jump on failing to find a match, and on balance this makes for a quicker search.

Consider that if we were looking for "ababcd" and we'd first found "abab…" (possible match so far), if the next character is c we still have a possible match. If it's a we don't have a match, but should jump forward two characters to start looking for a match starting from that. If it's anything else, we should jump ahead five characters and continue looking for there. Preparing the table to tell us how far to jump makes things much faster from then on:

public static int IndexOf(string haystack, string needle)
{
  if(haystack == null || needle == null)
    throw new ArgumentNullException();
  if(needle.Length == 0)
    return 0;//empty strings are everywhere!
  if(needle.Length == 1)//can't beat just spinning through for it
  {
    char c = needle[0];
    for(int idx = 0; idx != haystack.Length; ++idx)
      if(haystack[idx] == c)
        return idx;
    return -1;
  }
  if (needle.Length == haystack.Length) return needle == haystack ? 0 : -1;
  if (needle.Length < haystack.Length)
  {
    int m = 0;
    int i = 0;
    int[] T = KMPTable(needle);
    while(m + i < haystack.Length)
    {
      if(needle[i] == haystack[m + i])
      {
        if(i == needle.Length - 1)
          return m == haystack.Length ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - T[i];
        i = T[i] > -1 ? T[i] : 0;
      }
    }
  }
  return -1;
}      
private static int[] KMPTable(string sought)
{
  int[] table = new int[sought.Length];
  int pos = 2;
  int cnd = 0;
  table[0] = -1;
  table[1] = 0;
  while(pos < table.Length)
    if(sought[pos - 1] == sought[cnd])
      table[pos++] = ++cnd;
    else if(cnd > 0)
      cnd = table[cnd];
    else
      table[pos++] = 0;
  return table;
}

Solution 4

Try this:

internal bool SearchWord(string str, string searchKey)
{
    int j = 0; bool result = false;
    for (int i = 0; i < str.Length; i++)
    {
        if (searchKey[j] == str[i])
        {
            j++; //count++;
        }
        else { j = 0; }

        if (j == searchKey.Length)
        {
            result = true;
            break;
        }
    }
    return result;
}

View more solutions

Comments

[paxdiablo]

Why? If it's homework, you might want to tag it so we can target the answers towards you learning rather than being handed things on a platter. If it's not homework, use the string methods, that's what they're for.

[Gishu]

and why do you not want to use methods on the class you intend to inspect ?

[mpen]

Really guys? -1? It's not my fault if he wants to cheat on his homework and stifle his own learning; there are plenty of other ways to do that.

[Gishu]

My personal stand would be to not actively enable him to cheat. If I'm intrigued, I'd solve but not post. Its better to give him pointers or show him the way but don't spoonfeed.. there are enough bad programmers anyway.

[Jon Hanna]

The only differences I can see between this and the accepted answer is that where the accepted answer breaks out of the inner loop on a false and out of the outer loop on a match, this wastes time continuing.

[mpen]

Neat! I was wondering how you could make my solution faster. That KMPTable method could use some more describing, but I guess that's available on Wikipedia.