Algorithm

shortest-palindrome
給定一個(gè)字符串s，在s前增加最少字符串使得回文
還是上一周的算法
KMP實(shí)現(xiàn)方法：
KMP算法分享主要計(jì)算每個(gè)索引位置，前綴最長重復(fù)字符串表（文中最后分享）
反轉(zhuǎn)s為reverse，新字符串為s+"#"+reverse，找新字符串最后一位前綴匹配程度，即s前綴回文程度，只需要在s前補(bǔ)充反轉(zhuǎn)字符串剩余不回文的部分
比如：

public String shortestPalindrome(String s) {
        StringBuilder reverse = new StringBuilder(s).reverse();
        // reverse = abcbabcaba
        // newStr = reverse+"#" + s 即abcbabcaba#abacbabcba
        // 找newStr最后一位和前綴匹配程度，即s前綴的回文程度，需要補(bǔ)充的字符串為出去回文字符串剩余的反轉(zhuǎn)字符串
        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) {
        // 計(jì)算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) {
                    // 假設(shè)到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結(jié)束
                    t = f[t - 1];
                    if (t >= 0) {
                        if (temp == subStr.charAt(t)) {
                            f[i] = ++t;
                            break;
                        }
                    }
                }
            }
        }
        return f;
    }

Review

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

Tips

無

Share

KMP算法