串的表示和实现

定长顺序存储

直接定义数组 Sstring[MAXSTRLEN+1]

堆分配存储

1
2
3
4
5
typedef struct
{
	char *ch;
	int lenth;
}HString;

块链存储

image-20241125090558654

块链存储的实现

1
2
3
4
5
6
7
8
9
10
11
12
#define CHUNKSIZE 80
typedef struct Chunk //结点结构
{
	char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct
{
    Chunk *head,*tail;
    int curlen; 
}LString;

匹配模式算法

简单匹配模式算法

image-20241125091001386

简单来说：

  • 第一步，从头开始比较两个字符串
  • 如果短的那个字符串比较完了，并且没有出现不等的情况，说明已经匹配成功
  • 如果说出现了S[i] != T[j]的情况，说明在这个位置，出现了匹配失败，于是进行下一步
  • 字串T重新开始从第一个元素比较，主串S从上一次开始比较的元素的下一个位置开始比较
  • 用程序表达就是，S从i-j+2重新开始比较，t从j = 0重新开始比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define MAXSTRLEN 255
typedef unsigned char Sstring[MAXSTELEN+1]
int index(Sstring S,Sstring T,int pos)//传入的pos代表想要从主串的第几个位置开始比较
{
	i = pos;
    j = 1;
    while(i<=S[0] && j<=T[0])
    {
        if(s[i]==T[j])
        {
            ++i;
            ++j;
        }
        else //重新开始匹配
        {
            i=i-j+2;
            j = 1;
        }
    }
    if(j>T[0])
    {return i-T[0];} //返回位置
    else
    {return 0;}
}

时间复杂度

最好： 一次成功 -> O(m+n)

最坏： 最后一次成功 -> O(m*n)

KMP算法

核心思想：主串指针不回溯，模式串向后滑动至某个位置上

image-20241125105804817

  • 一个主串，且主串不回溯
  • 一个字串，且字串的每个元素伴随着next数组的一个值
  • next数组的意义是，当匹配失败的时候，下一次匹配可以跳过的字符个数
  • next数组的求法，是当前元素及之前元素构成的字符串中，前后元素一致的元素个数
  • 求next数组，使用递归的方法，比如说，现在有三个元素，其中第一个和最后一个元素一致，现在读取第四个元素，想要判断前两个和后两个元素是不是相等的，只需要在第一个元素和第三个元素相同的基础上再判断第二个元素和第四个元素相等与否，这个过程会产生两种结果：
  • 结果一 ： 元素2 和元素4相等，那么第四个元素的next数组值就是2
  • 结果二： 元素二和元素4不相等,那么开始寻找更短的
  • 在之前，我们已经判断了一段前后缀是相等的，这里有一个隐藏条件，就是这一对前后缀自己的前后缀与对方的使完全相等的，因此我们只需要找出上一次的前缀自身的前后缀，他们就是可以准备用于添加新元素后进行判断是否为新前后缀的一对前后缀

image-20241125115306013

比如这个，aba 和 aba 是已有的前后缀，加上b以后，与前面的c不一致，产生冲突

  • 对aba找前后缀，根据next数组，可知长度为1，即只有a一个

image-20241125115437507

  • 下面再对两个a后面两个元素

代码实现

计算next数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void build_next(const char *s, int *next) {
    int n = strlen(s); // 字符串长度
    next[0] = 0;       // 初始化第一个位置为 0
    int j = 0;         // j 指向前缀的末尾

    for (int i = 1; i < n; ++i) {
        // 不匹配时回退
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        // 如果匹配，前缀长度加 1
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j; // 记录当前位置的 next 值
    }
}