Knuth Morris Pratt (KMP) in C#. SearchResult ist ein Datenbehälter und wird hier deshalb nicht aufgeführt.
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;
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;
}