13-数据结构-串以及KMP算法，next数组

串

---

目录

串

一、串：

二、串的存储结构：

三、模式匹配

1.简单模式匹配（BF算法）

2.KMP算法

2.1-next（j）数组手工求解

2.2-nextval（j）数组手工求解

---

---

一、串：

内容受限的线性表，也就是相当于C语言里的字符串，只不过这里字符串从1开始存取。

此外串里包含子串，每个字串的第一个元素位置为该字串在串中的位置，每个串里面必有一个空串，此外，数串的时候，遇到重复的，只保留一个。

kmp算法就是根据相应的字串（模式串）取查找相应位置的操作，

串的长度，实际上为字符串长度。而数组长度为串的长度+1+1，从数组1开始存，因此+1，最后字符串结尾\'0’也要存。

二、串的存储结构：

静态顺序存储，就是定义一个固定长度的字符数组，再多一个记录个数的变量。

堆分配存储，就是动态数组，malloc一个空间，空间大小为sizeof（char）*(max+2);

块链存储：就是单链表的基础上，多了好多存储数据的变量，因此一块结点，好几个变量存进去。

串的基本操作：
SteCompare(S,T),就是C语言里的字符串比较，实际操作为：S-T，若结果小于0，则S<T，若结果大于0，则S大于T，S、T为字符串。

Concat(*T,S1,S2),给S2连接到S1后面，组成新的串，赋值给T串，返回。

SubStrin(*Sub,S,pos,len)，返回串S中，第pos位置起，长度为len的字串

Index（S,T,Pos），模式匹配，S中第pos位置起，与字串T相等的串。并返回该串再S中出现的第一次的位置。

三、模式匹配

1.简单模式匹配（BF算法）

模式匹配，就是有一个字串（模式串），取对应的主串里，找与它一样的，并返回它在主串中的位置，

简单模式匹配，就是主串在上，模式串在下，动主串坐标，取挨个对比。

设i为记录主串的下标，j为模式串的下标，k则是记录每次回溯，比对的次数。

当i和j中的值都相等时，都往后移动，当不匹配时，则进行下标的更新，主串中的i，更新为i=k+1，即主串的i从左至右，挨个比对，第一个开始，比对失败，则第二个开始，重新比对。模式串则时更新为j=1，因为，每次重新比对，所以，模式串每次更新都是从1开始。

简单模式匹配算法为（m*n）,主串长为m，模式串为n，因为最坏的情况，每次主串都要重新比对，所以为m，而每次比对，模式串都需要从头到尾重新遍历，所以m*n

2.KMP算法

        kmp时间复杂度为O（m+n），KMP算法主要是模式串下标动，更新，主串中的i会一直增加，不会出现回溯的现象。

2.1-next（j）数组手工求解

        在简单模式匹配的基础上，优化。即next（j）数组，是记录，每次模式串比对失败时，模式串下标的更新的起始值。如果模式串下标j==0，则i++，j++，即简单匹配操作，否则，主串不需要动，模式串下标更新动即可。

        而next(j)数组，怎么求嘞，next数组，就是给模式串每一个位置处，匹配失败，时，跟新的下标值都记录下来。所以手工怎么计算呢？

        分两部分，当第一个位置处时，j直接更新为0，因为第一个位置前，无数据，没法拿来进行找重复部分的长度。第二个位置时，则找第一个位置，然后错一位，进行比对，比对时，下面的那一串向右移动，直到比对完重复部分，之后重复部分长度+1，便是模式串下标所更新的值。

具体看讲义，不好画图

2.2-nextval（j）数组手工求解

        nextval数组，则是在，next的基础上，再优化。即，当next数组求的坐标的内容，与原来不匹配的坐标内容一致时，可直接，给nextval中，当前不匹配情况，与所求最新的，坐标相同即可。

具体看讲义，不好画图。