Knuth Morris Pratt (KMP) in C#. SearchResult ist ein Datenbehälter und wird hier deshalb nicht aufgeführt.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
if (pattern.Length > text.Length) return SearchResult.Empty(); SearchResult searchResult = new SearchResult() { Matches = new List() }; int[] prefixTable = CreatePrefixTable(pattern); for (int textIndex = 0, patternIndex = 0; textIndex < text.Length; textIndex++, patternIndex++) { if (text[textIndex] == pattern[patternIndex]) { if (patternIndex < pattern.Length - 1) continue; patternIndex = -1; searchResult.MatchCount++; searchResult.Matches.Add(new Match() { Position = textIndex - pattern.Length + 1 }); } else { if (patternIndex > 0) { patternIndex = prefixTable[patternIndex - 1] - 1; textIndex--; } } } return searchResult; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
private int[] CreatePrefixTable(string pattern) { int[] prefixTable = new int[pattern.Length]; prefixTable[0] = 0; //No pattern at position 0. for (int i = 1, j = 0; i < pattern.Length; i++) { if (pattern[i] == pattern[j]) { j++; prefixTable[j] = j; } else if(j > 0) { j = prefixTable[j - 1]; i--; } else { prefixTable[j] = 0; } } return prefixTable; } |