Algorithm

shortest-palindrome
給定一個字符串s座云，在s前增加最少字符串使得回文
還是上一周的算法
KMP實現(xiàn)方法：
KMP算法分享主要計算每個索引位置芝雪，前綴最長重復字符串表（文中最后分享）
反轉s為reverse，新字符串為s+"#"+reverse渣刷，找新字符串最后一位前綴匹配程度破花，即s前綴回文程度谦趣，只需要在s前補充反轉字符串剩余不回文的部分
比如：

public String shortestPalindrome(String s) {
        StringBuilder reverse = new StringBuilder(s).reverse();
        // reverse = abcbabcaba
        // newStr = reverse+"#" + s 即abcbabcaba#abacbabcba
        // 找newStr最后一位和前綴匹配程度，即s前綴的回文程度座每，需要補充的字符串為出去回文字符串剩余的反轉字符串
        String newStr = s + "#" + reverse;

        int[] f = calculateTable(newStr);
        for (int item : f) {
            System.out.print(item);
        }
        System.out.println();
        return reverse.substring(0, s.length() - f[newStr.length() - 1]) + s;
    }

public int[] calculateTable(String subStr) {
        // 計算table
        int[] f = new int[subStr.length()];
        f[0] = 0;
        int t = 0;
        char temp;
        for (int i = 1; i < subStr.length(); i++) {
            temp = subStr.charAt(i);
            if (temp == subStr.charAt(t)) {
                f[i] = ++t;
            } else {
                while (t > 0) {
                    // 假設到b不匹配前鹅，b之前匹配度為caca即t，t=4
                    // 拿caca繼續(xù)找匹配度(索引從0開始)t=f[t-1]=f[3]=2峭梳，s[t]=s[2]=c≠b
                    // 拿ca繼續(xù)找t=f[t-1]=f[1]=0匹配度為0結束
                    t = f[t - 1];
                    if (t >= 0) {
                        if (temp == subStr.charAt(t)) {
                            f[i] = ++t;
                            break;
                        }
                    }
                }
            }
        }
        return f;
    }

Review

distributed-system-microservices
提出了一些微服務基本的一些優(yōu)缺點

Tips

無

Share

KMP算法