Knuth Morris Pratt (KMP)

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