串

与栈和队列相似，串是内容受限的线性表，串的元素只能是字符

串中任意个连续字符组成的子序列称为该串的子串，真子串指不包含自身的所有子串

串的存储结构

顺序存储

#define MAXLENGTH 100
typedef struct SString{
    char data[MAXLENGTH + 1];
    int length;
}SString;

加一使位序与下标相等，data中第一个元素闲置不用，便于后续的计算

链式存储

#define CHUNKSIZE 50
typedef struct Chunk {
	char data[CHUNKSIZE];
	Chunk *next;
}Chunk;

typedef struck LString {
	Chunk *head, *tail;  // 串的头指针与尾指针
	int length;
}LString;

使用块链结构，一块的大小为CHUNKSIZE，以此来提高存储密度

串的模式匹配——KMP算法

确定主串中所含子串第一次出现的位置

详见【最浅显易懂的 KMP 算法讲解】 https://www.bilibili.com/video/BV1AY4y157yL/?share_source=copy_web&vd_source=fbe4b0e6c9f599f2e20ea27ac67af734

首先根据子串得出一个next数组，用来表示当匹配进行到该处时应该跳过子串前面的多少个字符，主串的i永远不递减

KMP算法思路是，当发现某个字符不匹配时，根据已经知道之前遍历过的字符来避免暴力算法中的回退步骤

已知next

int KmpSearch(char main[], char child[],int next[], int slen, int clen) {
    int i = 0, j = 0;
    while (i < slen) {
        if (main[i] == child[j]) {
            i++;
            j++;
        }
        else {
            if (j == 0) {
                i++;
            }
            else {
                j = next[j - 1];
            }
        }
        if (j == clen) {
            return i - j + 1;
        }
    }
    return -1;
}

当匹配时，i和j都加一
当匹配失败时，若j为零则i++；若j不为零，会根据最后一个匹配的字符的next值即next[j - 1]来作为j的值，此时i不加一
判断是否子串完全匹配成功，因为如果成功一定会执行子串最后一个字符匹配成功的结果，导致j++，此时j == clen
最后return的值是子串的第一位在主串中的位置

getNext

void getNext(char ch[], int len, int next[]) {
    next[0] = 0;
    int prefix_len = 0;  // 当前共同前后缀的长度,即next[j-1]
    int i = 1;
    while (i < len) {
        if (ch[i] == ch[prefix_len]) {
            prefix_len++;
            next[i] = prefix_len;
            i++;
        }
        else {
            if (prefix_len == 0) {
                next[i] = 0;
                i++;
            }
            else {
                prefix_len = next[prefix_len - 1];
            }
        }
    }
}

从i = 1开始，与第prefix_len位比对，初始为第0位
若相同则i与prefix_len均加一，并将prefix_len的值赋给next[i]
不相同则判断next数组上一个元素的值即prefix_len，为零则给next[i]赋值为零
若prefix_len不为零，以ABACABAB为例，进行至最后的B时，此时prefix_len = 3，最后的ABA与子串开头是相同的，因此前缀也相同，将prefix_len回溯为next[prefix_len - 1]，此时i不变，继续进行循环

test

int main() {
    char ch[] = {'a','b','a','c','a','b','a','b'};
    char s[] = "acbabacababa";
    int slen = sizeof(s);
    int clen = sizeof(ch);
    int* next = new int[clen];

    getNext(ch, clen, next);
    for (int i = 0; i < clen; i++) {
        printf("%d ", next[i]);
    }

    int place = KmpSearch(s, ch, next, slen, clen);
    printf("&& %d", place);

    delete[] next;
    return 0;
}