摘要：部分是回文的，在里面找是否有的。這里的范圍是，最小是，因為要保證是兩個單詞，最大是，這時候要找出另一個和他相反的串。判斷為回文，可以直接暴力，每個都判斷一次。兩個方向都找一遍就可能出現重復的情況，注意避免重復。例如，結果應該是。

鏈接：https://leetcode.com/problems...

這道題沒想出來思路，參考了這個博客的內容：
http://bookshadow.com/weblog/...

把一個單詞分為兩個部分：left, right。right部分是回文的，在words里面找是否有reverse的left。這里的left范圍是(0, len(word))，最小是0，因為要保證是兩個單詞，最大是len(word)，這時候要找出另一個和他相反的串。根據題目的意思，一個單詞只能用一次，而且words里面單詞都是unqiue的。
現在的問題就在于如果判斷right是否為回文，以及如何找到left的reverse串。判斷right為回文，可以直接暴力，每個right都判斷一次。找left可以用trie tree或者hashmap。可能出現ab, ccba這種第二個數比一個數長的情況，所以不光要從左到右看，還要從右往左看。兩個方向都找一遍就可能出現重復的情況，注意避免重復。

兩個詞形成的string一樣不算重復，只有當兩個詞的組合重復時才算重復。例如: ["", "aa"]，結果應該是[(0,1), (1,0)]。那么什么時候可能出現重復呢？["ab", "ba"]，這種兩個單詞形成了palindrome，如果在ab和ba的兩邊都查一遍肯定會重復。可以看出規律是當map里面有其中一個詞的reverse時，就少算一邊即可。

public class Solution {
    public List> palindromePairs(String[] words) {
        Map map = new HashMap();
        for(int i = 0; i < words.length; i++) {
            map.put(new StringBuilder(words[i]).reverse().toString(), i);
        }
        
        List> result = new ArrayList();
        for(int i = 0; i < words.length; i++) {
            String cur = words[i];
            int n = cur.length();
            for(int j = 0; j <= n; j++) {
                // left: (0, j), right: (j, n)
                // right is palindrome and find reversed left
                String left = cur.substring(0, j);
                String right = cur.substring(j, n);
                if(isPalindrome(right) && map.containsKey(left) && map.get(left) != i) {
                    result.add(Arrays.asList(i, map.get(left)));
                }
                
                // left is palindrome and find reversed right
                if(isPalindrome(left) && map.containsKey(right) && map.get(right) != i) {
                    // avoid duplication
                    if(j == 0 && map.containsKey(cur) && map.get(cur) != i) continue;
                    
                    result.add(Arrays.asList(map.get(right), i));
                }
                
            }
           
        }
        return result;
    }
    
    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) return false;
            i++; j--;
        }
        return true;
    }
}

這個博客還用了一種set的方法：
http://www.cnblogs.com/grandy...

暫時還沒看懂，明天再看下。。

題目鏈接：https://leetcode.com/problems...

這道題和“ Longest Palindromic Substring ” 是一個意思，不同的是這個palindrome string必須要從index = 0開始。最簡單的方法就是一個一個試。超時了。。。

這個算法是用來找最長回文字串的，利用的是回文的對稱信息或者說是prefix信息。

public class Solution {
    public String longestPalindrome(String s) {
        // base case 
        if(s == null || s.length() <= 1)  return s;
        // Manacher Algorithm
        /* new index: 0 1 2 3 4 5 6 
           old index: # 0 # 1 # 2 #
                        m   c   i r
        */
        // An array to store the max length at each center
        int n = s.length() * 2 + 1;
        int[] pivot = new int[n];
        pivotInitial(pivot, s);

        // find the maximum length
        int maxLen = 0;
        int center = 0;
        for(int i = 0; i < n; i++) {
            if(pivot[i] > maxLen) {
                maxLen = pivot[i];
                center = i;
            }
        }
        int lo = (center - maxLen) / 2;
        int hi = lo + maxLen;
        return s.substring(lo, hi);
    }

    // Manacher 
    /* new index: 0 1 2 3 4 5 6 
       old index: # 0 # 1 # 2 #
                  m   c   i r
    */
    private void pivotInitial(int[] arr, String s) {
        // center and maximum reachable index
        int c = 0, r = 0;
        for(int i = 0; i < arr.length; i++) {
            int diff = r - i;
            // mirror to i with pivot c
            int m = c - (i - c);
            // the maximum palindrome is in the reachable
            if(diff >= 0 && arr[m] < diff) {
                arr[i] = arr[m];
            }
            else {
                // if i > r, then just start from i
                int left = i / 2 - 1;
                int right = i / 2 + i % 2;
                // start from the index that exceed the reachable index
                if(diff >= 0) {
                    left -= diff / 2;
                    right += diff / 2;
                }
                // update center and maximum reachable
                arr[i] = len(s, left, right);
                c = i;
                r = i + arr[i];
            }
        }
    }

    private int len(String s, int left, int right) {
        while(left >= 0 && right <= s.length() - 1) {
            if(s.charAt(left) == s.charAt(right)) {
                left--;  right++;
            }
            else break;
        }
        return right - left - 1;
    }
    
}

這個算法是用來找substring的，利用的是substring自身的prefix信息。

// KMP algorithm

public class KMPSubstringSearch {

    /* compute the prefix array for the pattern string */
    private int[] prefixArray(String pattern) {
        int[] pre = new int[pattern.length()];
        // pre[0] = 0, pre[i] means the index of prefix
        // index used to store the position of matched prefix
        int index = 0;
        int i = 1;
        while(i < pattern.length()) {
            if(pattern.charAt(i) == pattern.charAt(index)) {
                pre[i] = index + 1;
                i++;  index++;
            }
            else {
                if(index == 0) {
                    pre[i] = 0;
                    i++;
                }
                else {
                    index = pre[index-1];
                }
            }
        }
        return pre;
    }

    // kmp, pattern match, return the position 
    // if no match, return -1
    private int kmp(String text, String pattern) {
        int[] pre = prefixArray(pattern);
        int i = 0; int j = 0;
        char[] ctext = text.toCharArray();
        char[] cpattern = pattern.toCharArray();
        while(i < ctext.length && j < cpattern.length) {
            // match
            if(ctext[i] == cpattern[j]) {
                i++;  j++;
            }
            // not match
            else {
                // first char of the pattern string
                if(j == 0) {
                    i++;
                }
                else {
                    j = pre[j-1];
                }
            }
        }
        if(j == cpattern.length) {
            return i-j;
        }
        else return -1;
    }

    public static void main(String args[]) {
        String text = "abdacabc";
        String pattern = "abc";
        KMPSubstringSearch test = new KMPSubstringSearch();
        int result = test.kmp(text, pattern);
        System.out.println(result);
    }
}