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 &gt; text.Length) return SearchResult.Empty();

            SearchResult searchResult = new SearchResult() { Matches = new List() };
            int[] prefixTable = CreatePrefixTable(pattern);

            for (int textIndex = 0, patternIndex = 0; textIndex &lt; text.Length; textIndex++, patternIndex++)
            {
                if (text[textIndex] == pattern[patternIndex])
                {
                    if (patternIndex &lt; pattern.Length - 1) continue; patternIndex = -1; searchResult.MatchCount++; searchResult.Matches.Add(new Match() { Position = textIndex - pattern.Length + 1 }); } else { if (patternIndex &gt; 0)
                    {
                        patternIndex = prefixTable[patternIndex - 1] - 1;
                        textIndex--;
                    }
                }
            }

            return searchResult;

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 &lt; pattern.Length; i++) { if (pattern[i] == pattern[j]) { j++; prefixTable[j] = j; } else if(j &gt; 0)
                {
                    j = prefixTable[j - 1];
                    i--;
                }
                else
                {
                    prefixTable[j] = 0;
                }
            }

            return prefixTable;
        }

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;

}