1
\$\begingroup\$

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
                    result.Add(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++;
                    }
                }
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ggorlen Oct 12 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.