【数据结构-陪读笔记】第四章（串） 408笔记目录指南

思维链条
文章图片

串是什么？

作用：为了存储一系列的可以是非数字的数据：比如名字，地址这些。
子串：一个串中的某一段。其位置用字串的第一个字母的下标来记录。
相等：值相等，且长度相等。
串中单引号不属于串，不计入长度中，仅仅作为区分常量。
空串&空格串：串里啥都没有，用 ? \varnothing ?表示；空格串里面有东西，是一堆空格。
串的所有操作都是基于串的定位操作。
基本操作：串赋值(StrAssign)，串比较(Strcompare)，求串长(StrLength)，串链接(StrConcat)，求子串(Substring)。串的其余操作简单，这里只说求字串。

串如何表示？定长法

人们最容易想到的就是开个数组了。但提前申请开个数组，必然不可能正正好好的开出来。可能长了，可能短了。放不下的话就只能“截断”了。
C中，为了方便确定串的长度，串的最后会加一个"\0"代表结束，不计入总长度，但是会占一个格子。没了这个，便无法确定串是不是结束了。
定长法的串的链接，这里用a串,b串,T串代替，必然有3种可能：1.a+b长度//P74的求字串的链接操作的批注代码 #define Max 25 typedef char String[Max + 1] //+1的意思是第一位被空出来当了String.length了Status StrConcat(String &T , String a , String b){ //第一种情况,足量 if(a[0] + b[0] <= Max){ T[1...a[0]] = s1[1...a[0]]; //a[0] = a.length,所以书上这么写 T[a[0]...a[0]+b[0]] = s2[1...b[0]]; //写入b T[0] = a[0] + b[0]; //控制长度 } //第二种：a够b不够，截取b else if(a[0] < Max){1.写a，2.写b，3.T[0]= Max} //第三种：a够b完全不够，不要b了 else{T[0...Max] = a[0...Max]} return ok; }
【代码批注p75】求子串：因为pos是"第"pos个字符开始算起的，就是从1开始.但s.length是从0开始的，所以s.length + 1 - pos。

模式匹配算法为什么要模式匹配？–因为这个我们最常用的基本操作“增删改查”。
人的直觉

我们怎么去思考“匹配问题”？–答：一个一个比，直到完全匹配上为止。
《数据结构》P79算法4-5解决的就是这个问题。

为什么出现了KMP？

可以看到一个明显的问题，4-5的算法某些步骤是非必要的。明知道下一个都不相等，还在那里使劲的比。
对于计算机而言，大多都是二进制，所以可能匹配了一堆数字，结果最后几位突然不一样了，白白浪费了时间。
KMP的问题目标就是：可不可以少比几次。
没有耐心看原理的，建议直接查看PPT演示的KMP算法

KMP的基本思路：P=Q=R，可以跳过很多多余的匹配问题。

文章图片

根据 next 函数进行匹配，如果两者匹配成功，则继续往后匹配；如果没成，让j往前跳转进行匹配。

int kmp(string s , string t , int pos){ int i = pos , j = 0 ; while(i < s.length() && j < t.length()){ if(j == 0 || s[i] == t[j]){i ++ , j ++; } //匹配成功，继续往后搜索 else j = next[j]; //如果发现不匹配，按照next指示跳转 } if(j > t.length()) return i - t.length(); else return error; }

next的代码通过上文可知，只要通过next数组，就可以经过跳转得到目标匹配的值。但是这也有了一个问题，如何去求得next的值？借鉴陈越老师关于kmp-next数组的ppt，可以看到：如果当前match[j - 1] + 1这个位置的数据与j这个位置的数据匹配成功，则相当于成功匹配，+1即可；如果不匹配(也就是b+1与j两个位置的值不匹配)，也没有必要从原来的第一个位置开始去寻找，由于a = b = c = d，所以只需要从a+1这个位置先去尝试匹配即可。

文章图片

//陈越老师的kmp-next版本 void get_next(string t , int next[]){ for(int j = 0 ; i < t.length() ; i ++){ int i = next[j - 1]; if(t[i + 1] == t[j]) next[j] = i + 1; //如果匹配成功，则继续+1 else i = next[i]; //如果匹配不成功，则回退到i中的上一个匹配到的位置（图中的a+1的那个位置） } }

【【数据结构-陪读笔记】第四章（串）】通过对比发现，两位老师的版本其实大同小异。其思路都是如果匹配，

//严蔚敏老师的kmp-next版本 //再次视为一个kmp算法 void get_next(string t , int next[]){ int i = 0 , j = 0; nest[0] = 0; while(i < t.length){ if(j == 0 || t[i] == t[j]) next[++ i] = ++ j; else j = next[j]; } }

KMP实现

这个是从-1开始的。
str.length()与str.size()都代表字符串的长度：length对应的是c中的strlen；而size是代表stl的一种求法，其实二者是类似的。而sizeof则代表了开辟空间的大小。由于前面曾经提到过，字符串是涵盖“\0”的，所以sizeof的长度总是要比length/size要大1。