字符串中找字串索引

暴破，直接處理從最開始匹配，從0-n開始循環(huán)查找，不相等重新計算
時間復(fù)雜度：O(n*m)

KMP算法處理找字符串中字串索引

如圖：當(dāng)"ABCDAB "失配時，直接移動到和"AB ABCD"處比較。

public Integer indexSubStr(String s, String subStr) {
        int[] f = calculateTable(subStr);

        int j = 0;
        for (int i = 0; i < s.length(); ) {
            if (s.charAt(i) == subStr.charAt(j)) {
                j++;
                if (j == subStr.length()) {
                    return i - (j - 1);
                }
                i++;
            } else {
                // 第一位沒匹配成功，i++繼續(xù)從j=0即字串第1位開始匹配
                if (j == 0) {
                   i++;
                } else {
                    // 有匹配成功的前綴，i不變，對齊匹配成功的前綴
                    // 匹配到"BBC ABCDAB "和"ABCDABD"時，" "和"D"不等
                    // 但"D"前綴f[j-1]為2即"AB"，i不動繼續(xù)和"ABCDABD"前綴之后比較，即"BBC ABCDAB "的"AB "和"ABCDABD"的"ABC"比較
                    j = f[j - 1];
                }
            }
        }

        return -1;
    }

關(guān)鍵計算前綴匹配表算法

cacacabc
caca
  caca

此時匹配成功，匹配+1

cacacabc
cacac
  cacab

不匹配找更短的匹配串，cacac和cacab因為不匹配找更短的，即前綴cacac的更短的串caca和cacab更短的串，有相同更短的串caca。caca是已經(jīng)匹配了的前綴，length = 4，而caca的匹配度等于匹配表中f[4-1]=f(3)位置

1. 所以cacac匹配失效時，減少1個匹配度，即已經(jīng)匹配了的caca的匹配度
2. 如果cacac的串caca無匹配前綴即時匹配為0，表示cacab的前綴串caca無法和當(dāng)前比較字符串匹配，結(jié)束，直接從失配處和子串第一位重新開始匹配;
3. 如果cacac的caca前綴有匹配，那么假設(shè)匹配2位表示cacab和前綴caca也匹配2位即ca，那么比較第三位b和當(dāng)前比較字符串第三位
4. 如果匹配則匹配度是3位，即匹配為2+1=3，匹配到cab
5. 如果不匹配則繼續(xù)找前綴ca的前綴匹無匹配結(jié)束有匹配繼續(xù)和b比較，如此匹配一直循環(huán)下去

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) {
                    // 假設(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;
    }

借鑒

shortest-palindrome-solution中KMP圖解
KMP算法詳解 前面講移動很清晰，講計算table不結(jié)合KMP圖解中的圖看更清楚