Tuesday, July 7, 2015

KMP algorithm

IndexOf Implementation :-

public static int[] FailureFunction(string p)
        {
            int[] F = new int[p.Length];
            F[0] = 0;
            int i = 1, j = 0;
            while (i < F.Length)
            {
                if (p[i] == p[j])
                {
                    F[i] = j + 1;
                    i++;
                    j++;
                }
                else if (j > 0)
                {
                    j = F[j - 1];
                }
                else
                {
                    F[i] = 0;
                    j++;
                }
            }
            return F;
        }

        public static int KMP(string s, string p)
        {
            int[] F = FailureFunction(p);
            int i = 0, j = 0;
            while (i < s.Length)
            {
                if (s[i] == p[j])
                {
                    if (j == p.Length-1)
                    {
                        return i - j;//match
                    }
                    else
                    {
                        i++; j++;
                    }
                }
                else
                {
                    if (j > 0)
                    {
                        j = F[j - 1];
                    }
                    else
                    {
                        i++;
                    }
                }

            }
            return -1;
        }

Node.JS rest api Tutorials