第六章串

串主要是由多个字符组成的有限序列，一般是以双引号来扩出（一些情况是单引号、java）。
传是一种特殊的线性表，数据元素之间呈现出线性关系
串的数据对象为字符集，在C语言中要求：可以用数组来表示字符串，但是要求最后一位必须是\0，数组可以不指定最后一位是0，但是要留有空位，该位置不计入串长。
串可以用顺序表（数组）或者是链表来存储，值得注意的是，串本质上还是int类型，只是根据ACSII表转换成了字符，区分字符3和数字3。
一般简单的串对象定义如下

char *a="123456";右面的123456是字符串常量，所谓常量就是这个值是保存在内存中的字符串常量区。每个字符串后面都有系统预设的结束符"\0",
char a[ ]="123456";//这个是将字符串保存在数组里。这个是数组初始化。相当于a[0]=1,a[1]=2;.......但是123456不是int变量、更不是常量，而是一个个的存储在字符数组中的字符元素。如果这一句是在函数中，那么123456是存储在栈上的函数中的数组当中。
而char a[10];a="123456";这种方法不可取，因为a是地址，是一个常量
串的实现比较容易，可以参考之前说的int类型实现队列还有链表，比较麻烦的是串的匹配
最常见的就是暴力匹配方法，简单来说就是一个长串中找小串

?这种实现如下

#include "stdio.h"

#define max 10

typedef struct {

??? char data[max];

??? int length;

}sstring;



int num(sstring s1, sstring s2) {

??? int num = 0;

??? if (s1.length < s2.length)

??? {

???????? printf("字符串数目不对");

???????? return 0;

??? }

??? else

??? {

???????? int i = 0, j = 0;

???????? int p = 0;

???????? while (i<= s1.length && j<= s2.length)//循环结束的标志位在于没有超出长度

???????? {

???????????? if (s1.data[i]==s2.data[j]) {//一旦判断出相同字符就会转到下一个字符

????????????????? i++;

????????????????? j++;

????????????????? p++;//这个标志位表示匹配成功的字符数目，达到s2.length后面就num++

???????????? }

???????????? else

???????????? {

????????????????? i = i - j + 1;

????????????????? //这个表达式很神奇，i-j保证没有匹配的话，这部分一定是0，+1又表示从下一个字符开始匹配

????????????????? j = 0;//一旦匹配第二个字符匹配不上，就会从0位开始

????????????????? p = 0;

???????????? }

???????????? //记录匹配的个数

???????????? if (p == s2.length) {

????????????????? num++;

????????????????? printf("i=%d",i );

????????????????? //一次匹配结束后就会从下一位继续匹配

????????????????? i = i - j + 1;

????????????????? j = 0;

????????????????? p = 0;

???????????? }

???????? }

??? }

??? return num;

}



int main()

{

??? sstring? sstring1 = { {"12f457f4"},8};

??? sstring sstring2 = { {"f45"},3 };

??? int a = num(sstring1, sstring2);

??? printf("\nhello");

??? return 0;

}

这种方法是最简单同时也是最暴力、费时的
另一种匹配的方法是：KMP算法
KMP算法是将：连续匹配成功的字符记下来，然后只需要移动至长串中出现这样字符的位置就可以了，换句话说节省了移动过程中之间数据的匹配

在王道的课上这样说道：

?我们对google其实有一种记忆，在第一次遮住的时候我们会感觉匹配很多googl，但是在最后一位e不匹配的时候，我们不会在从主串的第二位开始，而是期待主串的下一位（googl后一位）找到g来进行下一次匹配（比如就找到了o，不匹配，继续找后面的的g，进行匹配），

?这种情况下：主串没有回溯而是指向下一位，而模式串（匹配串）则是直接退回第一位了（要思考：为什么会退回第一位而不是其他位）

如果主串：googlogoogoogooglo

匹配串仍然是google

我们在第一次出现红色的位置停下来回朔匹配串到第一位g，主串不动，判断不是g后就会到下一位，这个时候绿色的四个位置都匹配上了，第五个位置没有匹配上；这个时候匹配串不是回溯到第一位，而是回溯到第二位o，然后主串和匹配串从第二位进行匹配。
找规律：似乎发现在主串在进行匹配的时候，主串不会再回溯了，匹配串回溯好像也不太彻底？

我们继续看这个例子

现在主串：abaacaabcabaabc
匹配串：abaabc
第一次匹配到红色c位置的时候匹配失败，主串不动，匹配串回溯到第二位，
第二次匹配红色c和匹配串第二位发现匹配失败，回溯到第一位
第三次匹配红色和匹配串第一位匹配，匹配失败，主串移动到下一位

……

一直匹配到绿色的ab，下一位c匹配失败匹配串回溯到第一位

……

进过无数次这种案例

似乎发现一个规律：

匹配串回溯和主串似乎没有任何的关系，似乎和匹配串本身有一定的关系，如果匹配串中的字符是完全不一样的，那么在主串匹配失败后必然停留后匹配串回溯到第一位。比如（主串acdabcdacdefg以及副串abcd）

现在一切都很清楚明了了：

根据匹配串本身的字符重复，会回溯不同的程度，完全不相同就会回溯到第一位（一定一定理解清楚，完全不匹配确实会让匹配串回溯到第一位）。

现在还有一个问题：怎么使用这个性质来实现匹配算法的改进？

答案是使用next数组，首先现根据匹配串来求出next数组，然后再根据next数组来优化主串匹配