0
\$\begingroup\$

KMP algorithm is for searching and matching string with a given pattern. The most important part is to build a table for the pattern then move a proper step rather than just one step increment.

In my code I created the table correctly but something is wrong for moving steps. It stuck in the for loop as variable was always equal to 2.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMP
{
    class Program
    {
        const string pattern = "abcdabd";
        const string s = "aadabcdabedxdfabcdabddsa";
        static int[] x = new int[7];
        static void Main(string[] args)
        {
            x = BuildTable(pattern);
            var y = Match(x, s);
            Console.WriteLine(y);
            Console.Read();
        }

        private static int Match(int[] x, string s)
        {
            int n = s.Length;
            int l = x.Length;
            int find = 0;
            Char[] charPattern = pattern.ToCharArray();
            for (int i = 0; i < n; )
            {
                string a = s.Substring(i, l);
                if (a.CompareTo(pattern).Equals(0))
                {
                    return i; // Found match, return match position of the first letter
                }
                // move position by BuildTable
                Char[] charSubstring = a.ToCharArray();
                int count = 0;
                for (int j = 0; j < l; j++)
                {
                    if (charPattern[j] == charSubstring[j])
                    {
                        count++;// count of matched chars
                        continue;
                    }
                    else
                    {
                        i += count - x[j]; // move forward steps = matched count - table value
                        break;
                    }
                }
            }
            return -999; // not found
        }

        public static int[] BuildTable(string p)
        {
            int[] result = new int[p.Length];
            result[0] = 0;
            for (int i = 1; i < p.Length - 1; i++)
            {
                // The substring from p[1] to p[i]
                string s = p.Substring(0, i + 1);

                var prefixes = Enumerable.Range(1, s.Length - 1)
                     .Select(a => s.Substring(0, a)).ToList();
                var suffixes = Enumerable.Range(1, s.Length - 1)
                     .Select(a => s.Substring(a, s.Length - a)).ToList();
                var common = prefixes.Intersect(suffixes).FirstOrDefault();
                result[i] = (common == null) ? 0 : common.Length;
            }
            return result;
        }
    }
}
\$\endgroup\$

closed as off-topic by svick, rolfl, konijn, Jamal Feb 8 '14 at 18:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – svick, rolfl, konijn, Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ If if (charPattern[j] == charSubstring[j]) is true, you never advance the i..... and loop infinitely. Closing off-topic. \$\endgroup\$ – rolfl Feb 8 '14 at 17:03
1
\$\begingroup\$

It is very hard to read your code, since you use single letter variables (x, s, l... etc.).

Some more general concerns: x is a class member, initialized in its declaration, overriden in the Main method (without the initial value ever being used), and then passed as an argument to the Match method.

As for why the value is stuck on 2, my guess is that the line i += count - x[j]; leaves the i value the same - count - x[j] == 0 perhaps you meant to write count + x[j]?

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.