首页 > 代码库 > 子字符查找KMP算法 - 子串自匹配索引表

子字符查找KMP算法 - 子串自匹配索引表

    public static int[] kmpTable(char[] seq) {
        int[] tbl = new int[seq.length];
        tbl[0] = 1;
        for (int i = 1; i < seq.length; i++) {// 子串最开始
            int j = tbl[i - 1];// 从已经算出的索引开始
            l1: for (; j <= i; j++) {
                for (int k = 0; j + k <= i; k++) {
                    if (seq[j + k] == seq[k] && j + k == i) {
                        break l1;// 完全匹配
                    } else if (seq[j + k] != seq[k] && k >= 1)// 子串内部自匹配
                        j += tbl[k - 1];
                }
            }
            tbl[i] = j;
        }
        return tbl;
    }

public static int[] kmpTable(char[] seq) {
int[] tbl = new int[seq.length];
tbl[0] = 1;
for (int i = 1; i < seq.length; i++) {// 子串最开始
int j = tbl[i - 1];// 从已经算出的索引开始
l1: for (; j <= i; j++) {
for (int k = 0; j + k <= i; k++) {
if (seq[j + k] == seq[k] && j + k == i) {
break l1;// 完全匹配
} else if (seq[j + k] != seq[k] && k >= 1)// 子串内部自匹配
j += tbl[k - 1];
}
}
tbl[i] = j;
}
return tbl;
}

子字符查找KMP算法 - 子串自匹配索引表