Study Leetcode 214 - shortest palindrome KMP algorithm

Leetcode214_ShortestPalindrome_KMP.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode214_shortestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Leetcode 214 shortest palindrome
        /// https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public String shortestPalindrome(String s)
        {            
            var temp = s + "#" + reverseString(s);

            var table = getTable(temp);
            var length = table.Length;

            //get the maximum palin part in s starts from 0
            return reverseString(s.Substring(table[length - 1])) + s;             
        }

        public string reverseString(string s)
        {
            var array = s.ToCharArray();
            Array.Reverse(array);
            return new string(array);
        }

        /// <summary>
        /// KMP table - interesting to learn
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int[] getTable(String s)
        {
            //get lookup table
            var length = s.Length;
            var table = new int[length];

            //pointer that points to matched char in prefix part
            int index = 0;

            //skip index 0, we will not match a string with itself
            for (int i = 1; i < length; i++)
            {
                if (s[index] == s[i])
                {
                    //we can extend match in prefix and postfix
                    table[i] = table[i - 1] + 1;
                    index++;
                }
                else
                {
                    // match failed, we try to match a shorter substring

                    // by assigning index to table[i-1], we will shorten the match string length, 
                    // and jump to the prefix part that we used to match postfix ended at i - 1
                    index = table[i - 1];

                    while (index > 0 && s[index] != s[i])
                    {
                        // we will try to shorten the match string length until we revert to the 
                        // beginning of match (index 1)
                        index = table[index - 1];
                    }

                    // when we are here may either found a match char or we reach the boundary and 
                    // still no luck so we need check char match
                    if (s[index] == s[i])
                    {
                        //if match, then extend one char 
                        index++;
                    }

                    table[i] = index;
                }

            }

            return table;
        }
    }
}