发布日期: 2023-12-10

串

本章是串这种结构的大体梳理

串的定义

串是由零个或多个字符组成的有限序列。

由于串实在过于常见，因此大多数语言都提供了一些基础的对串格式的支持，如C中的字符串拼接、复制、分割函数；C++中的string类，Java中的String类等。

很显然，不同的语言对串的支持程度不尽相同，因此这里仅仅提一个概念， 串的最小操作子集 ，即可以用这个集合里的函数实现任何想要对串进行的操作。

串赋值（CharAssign）
串复制（Strcopy）
串比较（StrCompare）
求串长（StrLength）
串连接（Concat）
求子串（SubString）

可以看出，其实串跟我们第一章所了解的 线性表 是很相似的，只不过，串存储的是一个个字符，同时串也常常以 一组字符 为单位进行增删改查，而不像线性表一样以 单个单元 为单位进行。

串的存储

串的堆分配存储

这种存储方式是串最常见的存储方式。其利用动态内存分配进行存储管理。

typedef struct {
    char *ch;
    int length;
} HString;

//当需要进行内存分配时
ch = (char*) malloc(length*sizeof(char));

其他存储方式

读者读到这里可能会产生两个疑惑：

直接用数组不行吗
想用链表存储

用数组，即被称为 串的定长顺序存储 ，其弊端在于无法改变串的长度，当进行操作时很容易产生长度过长的问题，这种情况下，数组存储只能进行截断操作，这导致了串内容的丢失。

用链表，即被称为 串的块链存储 ，其可以通过链表对串进行连接，同时链表每个节点中需要存储多少字符也可以由个人决定，但是这种存储方式使原本十分简单的复制、连接等操作变得极为复杂，一般不会采取这种存储方式。

串的模式匹配算法

通常，字串的定位操作被称为 串的模式匹配 ，表示为：

INDEX(S, T, pos);

其意义表示为：如果主串S中存在与字串T相同的串，则返回其在字串下标pos后第一次出现的位置。
这定义听着挺拗口的，读者不妨把它理解成字串查找即可。

我们现在想一想，如果要实现这个功能，该如何设计？

简单算法

这是我们大概第一眼就会想到的算法，主串从前往后循环，遇到与字串相同的字符则开始一个子循环流程，子循环能跑完，则代表着串匹配了，返回当前主串循环的下标。

int INDEX(char* S, char* T, int pos){
    int i = pos, j = 1;
    while(i <= S.length && j<= T.length){
        if(S[i] == T[j]){
            i++;
            j++;
        }else{
            i = i-j+2;
            j = 1;
            //匹配失败，指针回退
        }
    }
    if(j>T.length){
        return i - T.length;
        //说明子循环跑完了，有字串
    }else{
        return 0;
    }
}

这种算法固然清晰，但其时间复杂度为O(m*n)，即字串与主串的长度的乘积，这太长了。

首尾匹配算法

这种算法算得上一种折中，即每次比较时，优先比较首尾的元素，再比较中间的剩余元素，但由于这种算法并算不上真正降低了时间复杂度，这里不再详述。

KMP算法（重点）

KMP概述

我们再次甚至暴力求解的第一个算法，发现其实主要的重复计算时间来源，是主串中 每次字符失配时的指针回退 。如果我们能够达到一种主串中指针永远不回退的算法，那将大大降低我们的算法耗时。

我们这里举一个例子：

主串的内容：A B A B A B C

字串的内容：A B A B C

初始情况

如果按照暴力求解的算法，第一次匹配，字串匹配到了C，发现与主串的A不相同，则主串指针回退至B，字串指针回退至A，再次匹配。

但我们想的理想情况是将字串的A与主串中第三个A齐平，同时可以跳过重复的AB，直接从第三个字符开始比较。

理想情况

要实现这个跳跃过程，我们需要借助一个数组，这个数组的作用是当字串与主串的字符发生失配现象了，下一次比较时主串需要与哪一个字串中的字符相比较。

我们用具体的程序来表达一下这个算法：

int INDEX_KMP(char* S, char* T, int pos){
    int i = pos, j = 1;
    while(i<= S.length && j<= T.length){
        if(j == 0 || S[i] == T[j]){
            i++;
            j++;
            //当主串中的字符与字串的第一个字符失配，或者主串与字串还未失配时，继续向后比较
        }else{
            j = next[j];
            //此时失配，则j回退至next[j]所指向的位置，i不变
        }
    }
    if(j>T.length){
        return i-T.length;
    }else{
        return 0;
    }
}

next数组

那么现在的问题就从如何降低时间复杂度变为这个next数组该怎么求了。

这里原理不进行详细叙述，给出公式：
next[j] = 此前已成功匹配的字串中最长的相同前后缀+1

前缀，即不包含最后一个字符的字串（从前往后看）
后缀，即不包含第一个字符的字串（从后往前看）

特殊的，next[1] = 0

比如上例：
next

第一个字符A: next[1] = 0
第二个字符B: 不存在相同的前后缀，next[2] = 0+1 = 1
第三个字符A: 不存在相同的前后缀，next[3] = 0+1 = 1
第四个字符B: 前缀”A”与后缀”A”相等，next[4] = 1+1 = 2
第五个字符C: 前缀”AB”与后缀”AB”相等，next[5] = 2+1 = 3

nextval数组

next数组已经可以达到主串指针不回溯的目的了，但是还有最后一点点小遗憾：

我们假设字串为：A A A A B

我们假设程序在比较时，恰巧在B这一点失配了。接下来我们应该干什么？

根据我们此前的讲述：程序会根据 next[5] = 4 来将主串指针当前字符与字串的第四个字符A比较。

如果能够匹配还好，如果不匹配呢？

那就会出现，继续根据 next[4] = 3 、 next[3] = 2 …等等语句，与字串的第三个字符A，第二个字符A，第一个字符A，比了三次，然后发现，哦，第一个都对不上，那主串的指针往后移动一位。

发现问题了吗？字串的前几位其实都一样，那么如果我跟第四个字符A比完之后，其实再跟第三个、第二个、第一个A比较的过程完全可以省去，因为一定会失配。

这就是为什么我们会再引入一个数组，叫nextval，这个数组就是为了防止上述问题的发生而出现的。
其具体方法为：如果 next[j] == k ，同时字串中 T[j] == T[k] ，那么我们就不用让主串S再跟字串中T[k]比较了，因为必定失配，我们让S当前位置的字符直接跟 T[next[k]] 进行比较。

nextval的具体求法是通过next数组来的：