LeetCode 214. Shortest Palindrome
How to do it with KMP?
public class Solution { public string ShortestPalindrome(string s) { int len = s.Length; int mid = len/2; if(len % 2 == 1){ if(IsPal(s, mid,false)) return s; } for(int i = mid-1; i >= 0; i--){ if(IsPal(s, i, true)) return ConstrPal(s, i, true); if(IsPal(s, i, false)) return ConstrPal(s, i, false); } return ""; } private bool IsPal(string s, int i, bool isEven){ int left, right; if(isEven) { left = i; right = i+1; } else { left = i-1; right = i+1; } while(left >= 0){ if(s[left] != s[right]) return false; left -= 1; right += 1; } return true; } private string ConstrPal(string s, int i, bool isEven){ StringBuilder sb = new StringBuilder(); if(!isEven) sb.Append(s[i]); for(int j = i+1; j < s.Length; j++){ sb.Append(s[j]); sb.Insert(0, s[j]); } return sb.ToString(); } }