# Moving steps in KMP algorithm [closed]

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;

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

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

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

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

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]?