[每天默写一个算法]KMP
作业要求：默写String的KMP算法。
KMP是经典的字符串匹配算法。复杂度为O(m+n)
|
String的KMP |
|
public static class StringHelper { public const int KMPNoMatch = -1; public static int KMP(this string source, string pattern) { if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(pattern)) { return KMPNoMatch; } var i = 0; var j = 0; var result = KMPNoMatch; var nextVal = GetNextVal(pattern);
while (i < source.Length && j < pattern.Length) { if (j == -1 || source[i] == pattern[j]) { i++; j++; } else { j = nextVal[j]; } }
if (j >= pattern.Length) { result = i - pattern.Length; }
return result; }
private static int[] GetNextVal(string pattern) { var j = 0; var k = -1; var result = new int[pattern.Length];
result[0] = -1;
while (j < pattern.Length - 1) { if (k == -1 || pattern[j] == pattern[k]) { j++; k++; if (pattern[j] != pattern[k]) { result[j] = k; } else { result[j] = result[k]; } } else { k = result[k]; } }
return result; } } |
字符串能匹配，其他类型的串也就可以匹配。下面是数组的KMP匹配算法。
|
数组的KMP |
|
public static class ArrayHelper { public const int KMPNoMatch = -1; public static int KMP( this Array source, Array pattern) { if (source == null || pattern == null || source.Length == 0 || pattern.Length == 0) { return KMPNoMatch; } var i = 0; var j = 0; var result = KMPNoMatch; var nextVal = GetNextVal(pattern);
while (i < source.Length && j < pattern.Length) { if (j == -1 || source.GetValue(i) == pattern.GetValue(j)) { i++; j++; } else { j = nextVal[j]; } }
if (j >= pattern.Length) { result = i - pattern.Length; }
return result; }
private static int[] GetNextVal(Array pattern) { var j = 0; var k = -1; var result = new int[pattern.Length];
result[0] = -1;
while (j < pattern.Length - 1) { if (k == -1 || pattern.GetValue(j) == pattern.GetValue(k)) { j++; k++; if (pattern.GetValue(j) != pattern.GetValue(k)) { result[j] = k; } else { result[j] = result[k]; } } else { k = result[k]; } }
return result; } } |
泛型数组也有KMP匹配算法。
|
泛型数组的KMP |
|
public static class IListHelper { public const int KMPNoMatch = -1; public static int KMP<T>( this IList<T> source, IList<T> pattern) { if (source == null || pattern == null || source.Count == 0 || pattern.Count == 0) { return KMPNoMatch; } var i = 0; var j = 0; var result = KMPNoMatch; var nextVal = GetNextVal(pattern);
while (i < source.Count && j < pattern.Count) { if (j == -1 || source[i].Equals(pattern[j])) { i++; j++; } else { j = nextVal[j]; } }
if (j >= pattern.Count) { result = i - pattern.Count; }
return result; }
private static int[] GetNextVal<T>(IList<T> pattern) { var j = 0; var k = -1; var result = new int[pattern.Count];
result[0] = -1;
while (j < pattern.Count - 1) { if (k == -1 || pattern[j].Equals(pattern[k])) { j++; k++; if (pattern[j].Equals(pattern[k])) { result[j] = k; } else { result[j] = result[k]; } } else { k = result[k]; } }
return result; } } |
原文：http://www.cnblogs.com/bitzhuwei/p/algorithm_kmp.html