五. 串

串是由零个或多个字符组成的有限序列，又名叫字符串。
朴素的模式匹配算法

#define String char*

/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。*/
int Index(String S, String T, int pos) {
    int i = pos; //i用于主串S中当前位置下标，若pos不为1则从pos位置开始
    int j = 1; //j用于子串T中当前位置下标值
    while (i <= S[0] && j <= T[0]) { //若i小于S长度且j小于T的长度时循环
        if (S[i] == T[i]) { //两字母相等则继续
            ++i;
            ++j;
        } else { //指针后退重新开始匹配
            i = i - j + 2; //i退回到上次匹配首位的下一位
            j = 1; //j退回到子串T的首位
        }
    }
    if (j > T[0]) {
        return i - T[0];
    } else {
        return 0;
    }
}

KMP模式匹配算法

为了避免重复遍历的情况，三位前辈发表了一个模式匹配算法，称之为克努特-莫里斯-普拉特算法，简称KMP算法。

void get_next(String T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) { //此处T[0]表示串T的长度
        if (j == 0 || T[i] == T[j]) { /*
                                       T[i]表示后缀的单个字符
                                       T[j]表示前缀的单个字符
                                       */
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j]; //若字符不相同，则j值回溯
        }
    }
}

int Index_KMP(String S, String T, int pos) {
    int i = pos;
    int j = 1;
    int next[255];
    while (i < S[0] && j <= T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    if (j > T[0]) {
        return i - T[0];
    } else {
        return 0;
    }
}

对get_next函数进行改良

void get_nextval(String T, int *nextval) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}d4dd