KMP-字符串匹配

//构建Next数组
vector getNext(string str) {
    vector next;
    next.push_back(-1);
    int j = 0, k = -1;
    while (j < str.length() - 1) {
        if (k == -1 || str[j] == str[k]) {
            next.push_back(++k);
            ++j;
        } else {
            k = next[k];
        }
    }
    return next;
}

//dad为原字符串
//son为模式串
//输出：原字符串中模式串所有出现位置的索引
vector KMP(vector next, string dad, string son) {
    vector index;
    int j = 0, i = 0;
    while (i < dad.length()) {
        if (j == -1 || dad[i] == son[j]) {
            i++;
            j++;
            if (j == son.length()) {
                index.push_back(i - j);
                i = i - j + 1;
                j = 0;
            }
        } else {
            j = next[j];
        }
    }
    return index;
}