CODEWITHSUNDEEP
c#stringsubstring
Nikhil Tamhankar
Nikhil Tamhankar

Reputation: 439

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

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.

Upvotes: 2

Views: 22611

Answers (7)

debashis panda
debashis panda

Reputation: 1

public static findindex(String str,String substr)
 {
     char a[]=str.toCharArray();
     char b[]=substr.toCharArray();
     int j=0,t=0;
     for(int i=0;i<str.length()&&j<substr.length();i++)
       {
       if(a[i]==b[j])
          {
            t=i;
            j++;
          }
       else
       continue;
       }
      if(t==0)
      return -1;
      else
      return t-substr.length()+1;
      }//in java

Upvotes: 0

user5385373
user5385373

Reputation: 11

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;
}

Upvotes: 1

Jon Hanna
Jon Hanna

Reputation: 113272

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;
}

Upvotes: 1

sathish Kumar
sathish Kumar

Reputation: 1

        string mainString = Console.ReadLine();
        string subString = Console.ReadLine();
        for (int i = 0; i <= mainString.Length - subString.Length; i++)
        {
            bool match = true;
            for (int j = 0; j < subString.Length && mainString[i + j] != subString[j]; j++)
            {
                match = false;
            }
            if (match)
                Console.WriteLine(i);
        }

Upvotes: 0

Pratik
Pratik

Reputation: 11745

Try this:

public static string BetweenOf(string ActualStr, string StrFirst, string StrLast)  
{ 
    return ActualStr.Substring(ActualStr.IndexOf(StrFirst) + StrFirst.Length,
          (ActualStr.Substring(ActualStr.IndexOf(StrFirst))).IndexOf(StrLast) + StrLast.Length);    
}

Upvotes: 0

mpen
mpen

Reputation: 282885

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;
    }
}

Upvotes: 6

Jeff
Jeff

Reputation: 36573

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...

Upvotes: 5

Related Questions