串的顺序存储结构和KMP匹配算法

  • A+

串其实就是字符串,字符串其实就是由字符组成的有限序列,同线性表差不多,只不过它的元素为字符了,但是不同的是,线性表注重的是单个元素的操作,而串一般都是对多个元素的操作

串的顺序存储结构和KMP匹配算法

有的字符串以字符‘\0’表示结束,0下标数值元素存储字符串的长度。这里因为c#的数组是Array派生,它是需要实例化的,是个引用,我们可以为它赋予一个新的空间,所以这里将使用数组长度来约束字符串,得知它的结尾就是最后一个元素,字符串的长度就是数组的长度,下面开始实现。

 


_data是一个char数组类型。两个构造函数,一个调用ValueTo初始化字符串为chars,一个赋值为null,表示为空字符串,其中ValueTo是用字符数组赋值给_data,初始化或重新分配空间给_data数组,长度为赋值chars的长度,遍历每个char元素赋值给_data的对应位置。

 


用串来赋值

 

①先判断s字符串是否为空就是判断数据域_data是否为null

②获取到s串的长度,重构或初始_data数组的大小

 

③遍历整个串的长度,通过GetCharByIndex获取对应位置的字符,赋值给_data数据域的对应位置


插入字符数组到指定位置

①先判断本串和字符数组是否为空

②判断索引的合法性

③临时保存本串的数据

④重构本串的数据域大小为原串长度+插入字符数组长度

⑤原串index前的字符,插入的字符,原串index和其后的字符,分为三段分别按顺序赋值给新的数据域

串的顺序存储结构和KMP匹配算法

 


删除指定位置长度的字符串

①同样的需要判断串是否为空和索引的合法性

②临时保存原串的数据

③重构数据域大小为删除字符串后的长度

④遍历赋值,通过go位移跳过被删除的元素

串的顺序存储结构和KMP匹配算法

 


这里是截取字符数组或字符串指定位置长度的字符,插入到主串指定位置中

 

①先判断length是否为0,是的话取length为最长的长度

②截取出指定位置长度的字符

判断字符数组是否为空,判断位置和长度的合法性,新建length长度的数组,遍历源字符数组,复制指定位置的字符到新数组中,返回

 

③判断一下截取出来的字符数组是否为空

④将截取出来的字符数组,插入到主串的(这个方法前面讲过),下面那个方法调用有个ToChars()方法,它是将字符串类转换位一个字符数组,并返回

你会发现,这里也是使用subChar直接截取整个字符数组的

 


取出一个子串

①截取出指定位置长度的字符数组

②判断这个字符数组是否为空

③新建一个串,并初始化为这个字符数组

④返回新建的串

 


以自身为主串,在尾部链接s串

①判断主串和链接串是否为空

②得出他们的长度

③临时保存主串的字符数据

④重构主串数据域的长度为两串相加的长度

⑤分两段分别赋值为新的数据域,一段是原主串的数据,一段是链接的串的数据

 


这个就是调用已经写好的方法,可以参考这些方法

①判断两串是否为空

②新建一个空串

③赋值为本串的字符

④再用新串链接s串

⑤返回新串

 


通过遍历查找子串的位置,没有找到返回0

①先检查主串和匹配串是否为空

②得到它们的长度

③在指定的主串i = pos位开始

④不断截取出与匹配长度的子串与匹配串比较,直到找到与匹配串相匹配的串,返回它的位置i,或者截取的子串长度小于匹配串长度了

串的顺序存储结构和KMP匹配算法
串的顺序存储结构和KMP匹配算法
串的顺序存储结构和KMP匹配算法


如果字符串很长,匹配的字符串也很长

例如000000000000000000000000000001

匹配00000000000001

这样还是采用朴素的匹配方法的话,需要比较的次数是很多的,每次i的循环比较,都要比较到最后字符才能知道不相等,计算机的数据是0和1的世界,如果使用这种方法是不效率的,是很恐怖的,所以下面是KMP算法。

 


KMP匹配算法:

串的顺序存储结构和KMP匹配算法

!!!KMP算法可以跳过这些没必要比较的循环!!!

 


通过匹配串,得出nextvalue[index]数组,index就是匹配不相等的匹配串位置,这里需要得出所有位置,因为你也不知道哪里不匹配,保存的数据就是index位置前面字符串前后缀字符相同个数+1,特殊的index = 1时,值为0

串的顺序存储结构和KMP匹配算法

也就是说7号位置匹配不成功后,就跳到四号位,为什么呢,看图

串的顺序存储结构和KMP匹配算法

!!!KMP算法可以减少对某次循环中某些相同字符的重复比较!!!

 


下面看一下nextvalue的求法

这里直接说一下例子吧!

例如匹配串T = "ababaaaba"

①nextval[1] = 0;

②j = 0   : i++=2 , j++ = 1; nextval[2] = 1;   字符串"a"

③j = 1,i = 2 ,"a" != "b" : 回溯 j = nextval[j] = 0  字符串"ab",j = 0表示回到了最头部,没有一个相等

串的顺序存储结构和KMP匹配算法

④j = 0  : i++ = 3 , j++ = 1 ;

串的顺序存储结构和KMP匹配算法

但因为3和1位置都是'a'。(我3号位的'a'匹配不相等了,那我回到1号位也是'a',也是不相等)。所以这是没必要的,直接回溯到1号位的回溯,nextval[3] = nextval[1] = 0;   字符串"ab"

⑤j=1,i=3,'a'='a' :i++=4,j++=2 ;

串的顺序存储结构和KMP匹配算法

同理的4和2的字符也相等,也没必要回溯到2,nextval[4] = nextval[2] = 1;

⑥j=2, i=4, 'b' = 'b' :i++ = 5, j++=3; 5和3的字符相同,则nextval[5] = nextval[3] = 0

⑦j = 3, i = 5 ,'a' = 'a' : i++=6,j++4 ,6和4的字符不相等,可以回溯到4号位则nextval[6] = j = 4。你可以发现,j一直在往后记录着前后缀相同个数+1,而i就是遍历的位置,也可以说是后缀字符

⑧j = 4, i = 6 ,‘b’!='a':有不相等了,j 就会回溯到前面相等的地方,j = nextval[j] = nextval[4] = 1,再来 j = 1,i = 6 ,'a'='a':i++=7,j++=2,7和2的字符不相等,则nextval[7] = 2

⑨往下就不讲了,自己推吧!

 


其实这个跟获取nextval数组差不多,同样使用i向后遍历字符,i不会较小,而j就是用来记录字符相同个数+1,如果有某个地方不相同了,就回到上一次有相同的地方

串的顺序存储结构和KMP匹配算法
此时j就要回到nextval[5],而i不变

串的顺序存储结构和KMP匹配算法

此时5和3相同,主串就可以走向下一轮循环,j也要+1

串的顺序存储结构和KMP匹配算法
此时4和6不等,j就要回到nextval[4] = 0,表示没有相同的了,可以下一轮循环了

................................

 


测试

 

结果

串的顺序存储结构和KMP匹配算法
串的顺序存储结构和KMP匹配算法

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: