# C# KMP algorithm

I tried to implement KMP algorithm on my own and found it kind of hard to follow. Can you please comment how would you make this code easier to read / understand.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{
[TestClass]
public class KMPAlgorithmTest
{
[TestMethod]
public void TestMethod1()
{
string input = "abcdefgh";
string pattern = "def";
Assert.AreEqual(3, KMP.FindSubString(input, pattern)[0]);
}

[TestMethod]
public void TestMethod2()
{
string input = "abcdabcabcdf";
string pattern = "abcdf";
Assert.AreEqual(7, KMP.FindSubString(input, pattern)[0]);
}

//naive algo O(n*m)
[TestMethod]
public void WorstCaseTest()
{
string input = "aaaaaaab";
string pattern = "aaab";
Assert.AreEqual(4, KMP.FindSubString(input, pattern)[0]);
}

[TestMethod]
public void FailTest()
{
string input = "aaaaaaab";
string pattern = "ggg";
Assert.AreEqual(0,KMP.FindSubString(input, pattern).Count);
}
}

public class KMP
{
public static List<int> FindSubString(string str, string pattern)
{
List<int> result = new List<int>();
int strLength = str.Length;
int pLength = pattern.Length;
if (strLength < pLength)
{
return result;
}

//the longest prefix suffix
// we allocate a memory with Pattern size
int[] lps = new int[pLength];
ComputeLps(lps, pLength, pattern);

int j = 0; // index for pattern
int i = 0; // index for str
while (i < strLength)
{
if (pattern[j] == str[i])
{
j++;
i++;
}

if (j == pLength)
{
//pattern is found at index i-j
j = lps[j - 1];
}
else if (i < strLength && pattern[j] != str[i])
{
if (j != 0)
{
j = lps[j - 1];
}
else
{
i = i + 1;
}
}
}

return result;
}

private static void ComputeLps(int[] lps, int pLength, string pattern)
{
int len = 0;
int i = 1;
lps[0] = 0; // lps[0] is always 0

while (i < pLength)
{
if (pattern[i] == pattern[len])
{
len++;
lps[i] = len;
i++;
}
//(pattern[i] != pattern[len])
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = len;
i++;
}
}
}
}
}
}

• This is Knuth-Morris-Pratt string searching algorithm, for those who don't know what KMP means off the top of their head. A bit more context and exposition of how it works on the part of OP would be helpful. – ggorlen Oct 12 '19 at 22:06