<commit_before>package com.fishercoder.solutions;

/**
 214. Shortest Palindrome

 Given a string S, you are allowed to convert it to a palindrome
 by adding characters in front of it.
 Find and return the shortest palindrome you can find by performing this transformation.

 For example:

 Given "aacecaaa", return "aaacecaaa".

 Given "abcd", return "dcbabcd".
 */
public class _214 {

    public static class Solution1 {
        /**credit: https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation*/
        /**
         * TODO: read it explanation and understand KMP completely.
         */
        public String shortestPalindrome(String s) {
            String temp = s + "#" + new StringBuilder(s).reverse().toString();
            int[] table = getTable(temp);
            //get the maximum palin part in s starts from 0
            return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
        }

        public int[] getTable(String s) {
            //get lookup table
            int[] table = new int[s.length()];

            //pointer that points to matched char in prefix part
            int index = 0;
            //skip index 0, we will not match a string with itself<commit_msg>refactor 214<commit_after>package com.fishercoder.solutions;

public class _214 {

    public static class Solution1 {
        /**credit: https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation*/
        /**
         * TODO: read it explanation and understand KMP completely.
         */
        public String shortestPalindrome(String s) {
            String temp = s + "#" + new StringBuilder(s).reverse().toString();
            int[] table = getTable(temp);
            //get the maximum palin part in s starts from 0
            return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
        }

        public int[] getTable(String s) {
            //get lookup table
            int[] table = new int[s.length()];

            //pointer that points to matched char in prefix part
            int index = 0;
            //skip index 0, we will not match a string with itself
{'fraction_non_alphanumeric': 0.10293453724604966, 'fraction_numerical': 0.014446952595936794, 'mean_word_length': 2.2540381791483113, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3428197', 'n_tokens_mistral': 621, 'n_tokens_neox': 575, 'n_words': 206}