KnuthMorrisPrattSearcher.cs

usingSystem.Collections.Generic;

namespaceAlgorithms.Strings.PatternMatching;

publicclassKnuthMorrisPrattSearcher
{
/// <summary>
/// An implementation of Knuth–Morris–Pratt Algorithm.
/// Worst case time complexity: O(n + k)
/// where n - text length, k - pattern length.
/// </summary>
/// <param name="str">The string to look in.</param>
/// <param name="pat">The pattern to look for.</param>
/// <returns>
/// The zero-based positions of all occurrences of <paramref name="pat" /> in <paramref name="str" />.
/// </returns>
publicIEnumerable<int>FindIndexes(stringstr,stringpat)
{
varlps=FindLongestPrefixSuffixValues(pat);

for(inti=0,j=0;i<str.Length;)
{
if(pat[j]==str[i])
{
j++;
i++;
}

if(j==pat.Length)
{
yieldreturni-j;
j=lps[j-1];
continue;
}

if(i<str.Length&&pat[j]!=str[i])
{
if(j!=0)
{
j=lps[j-1];
}
else
{
i+=1;
}
}
}
}

/// <summary>
/// Return the longest prefix suffix values for pattern.
/// </summary>
/// <param name="pat">pattern to seek.</param>
/// <returns>The longest prefix suffix values for <paramref name="pat" />.</returns>
publicint[]FindLongestPrefixSuffixValues(stringpat)
{
varlps=newint[pat.Length];
for(inti=1,len=0;i<pat.Length;)
{
if(pat[i]==pat[len])
{
len++;
lps[i]=len;
i++;
continue;
}

if(len!=0)
{
len=lps[len-1];
}
else
{
lps[i]=0;
i++;
}
}

returnlps;
}
}