String Search Algorithm

This article does not attempt to teach you how to write high performance string matching algorithms, nor does it try to explain the algorithms that are presented. If you're looking for that kind of information, consult an algorithms book such as Knuth or Cormen, et al. An excellent online reference for string matching algorithms is the Handbook of Exact String Matching Algorithms.

Using in code 

1. Naive Search Algorithm 

Slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches.

Example :- 

public static int[] SearchString(string str, string pat)
        {
            List<int> retVal = new List<int>();
            int M = pat.Length;
            int N = str.Length;

            for (int i = 0; i <= N - M; i++)
            {
                int j;

                for (j = 0; j < M; j++)
                {
                    if (str[i + j] != pat[j])
                        break;
                }

                if (j == M)
                    retVal.Add(i);
            }

            return retVal.ToArray();

        }


static void Main(string[] args)

        {
            string str = "String Search Algorithm in c#";

            var searchStr = "Algo";
int[] value = SearchString(str, searchStr);

        }

2. Boyer-Moore String Search Algorithm :- Unlike the previous pattern searching algorithms, algorithm starts matching from the last character of the pattern. This algorithm considered as the most efficient string-matching algorithm in usual applications.

Example

public static int[] SearchStringByBoyer(string str, string searchStr)

        {

            List<int> retVal = new List<int>();

            int m = searchStr.Length;

            int n = str.Length;

            int[] badChar = new int[256];

            BadCharHeuristic(searchStr, m, ref badChar);

            int s = 0;

            while (s <= (n - m))

            {

                int j = m - 1;

                while (j >= 0 && searchStr[j] == str[s + j])

                    --j;

                if (j < 0)

                {

                    retVal.Add(s);

                    s += (s + m < n) ? m - badChar[str[s + m]] : 1;

                }

                else

                {

                    s += Math.Max(1, j - badChar[str[s + j]]);

                }

            }

            return retVal.ToArray();

        }

       

        private static void BadCharHeuristic(string str, int size, ref int[] badChar)

        {

            int i;

            for (i = 0; i < 256; i++)

                badChar[i] = -1;

            for (i = 0; i < size; i++)

                badChar[(int)str[i]] = i;

        }

static void Main(string[] args)

        {

            string str = "String Search Algorithm in c#";

            var searchStr = "Algo";

int[] value = SearchString(str, searchStr);

       }

IndexOf :- We can use IndexOf function of string to search the substring in string.

Example:- 

static void Main(string[] args)

        {

            string str = "String Search Algorithm in c#";

            var searchStr = "Algo";

             int minIndex = str.IndexOf(search);

            while (minIndex !=-1)

            {

                Console.WriteLine(minIndex.ToString());

                minIndex = str.IndexOf(search, minIndex + search.Length);

            }