第四章——串

字符串存储

一般有定长空间分配法，不定长分配两种方式。

后者以 \0 字符来作为字符串结尾，前者需要再存储一个字符串长度，超出长度之外的字符是无效的。

串的模式匹配算法

假设主串长度为 n，模式串长度为 m。

暴力匹配即对于每一个可能出现模式串的位置（n）对模式串进行匹配判断（m），时间复杂度显而易见的是 O（mn）。

KMP算法会构建一个 Next 数组，在匹配的时候，每一次失配，我们都让模式串指针跳转到 next[j] 的位置上去，主串位置不变。

构建Next数组的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<n;i++){
    int t=next[i];
    while(t!=1&&s[i]!=s[t]){
        t=next[t];
    }
    if(s[t]==s[i]){
        next[i+1]=t+1;
    }
    else{
        next[i+1]=1;
    }
}
next[1]=0;

匹配的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find_str(char *s1,char *s2){
    int n=strlen(s1+1),m=strlen(s2+1);
    int i=0,j=0;
    while(i<=n&&j<=m){
        if(j==0||s[i]==s[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }
    return j==m+1;
}

next数组的值，如果字符串下标是从0开始的，那么当前next数组的值等以不包括当前字符的前缀为子串，对子串进行最大公共真前后缀的长度值。特别的，第一个值为-1。

如果是 1 开始的，那么值整体 + 1。因为第一位失配，我们需要做的应该是模式串和主串都后移一位，用于特判。

对于KMP的改进，就是如果自己和next值的数是相等的，那么直接把next的值指向自己next值的next值即可。

其它没有什么内容了，也不会考算法题。