《大话数据结构》笔记 - 第5章 串

字符串大小的定义

两种情况下字符串一小于字符串二：

• 前一个字符串是另一个字符串开始的部分，例如hap和happen。
• 两个字符串第一个不同的字符前一个小于后一个，例如happen和happy。

串的存储形式通常是使用顺序存储结构，链式存储结构只在拼接和断开字符串的时候具有性能优势，在其他方面不如顺序存储结构更具有优势。

字符串的模式匹配

朴素模式匹配

就是最简单的从第一个字符开始依次匹配。

KMP模式匹配

推导next数组的公式

$$next[i]=\left\{ \begin{aligned} 0 & & 当j=1时 \\ Max(k | 1<k<j, 且‘p_1-p_{k-1}’=‘p_{j-k+1}-p_{j-1}’) & & 此集合不为空时 \\ 1 & & 其他情况下 \end{aligned} \right.$$

void getNext(char *p, int *next)
{   
    int i = 0, j = -1;
    
    while (i < strlen(p)) { 
        if (j == -1 || p[i] == p[j]) { //情况1
            ++i;
            ++j;
            next[i] = j;    //匹配则自增，不匹配的字符串都会导致j==-1之后第一个给0,之后判断后面是否有匹配。
        } else {            //情况2
            j = next[j];    //图5-7-4右下角子图讲的子串的j也不必重头开始。
        }
    }
}

对于一个匹配串”abcabd”来说，第一个a肯定是0,后面b的时候先进条件1将其给0之后判断next[i]和next[j]是否匹配，匹配就继续找，不匹配就将j复位。

应用上面的getNext得到匹配算法