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;
}
}
}
if (charPattern[j] == charSubstring[j])
is true, you never advance thei
..... and loop infinitely. Closing off-topic. – rolfl♦ Feb 8 '14 at 17:03