字符串操作(算法与数据结构课程设计)(2)

该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

max{ k|0<k<j,且“p0 pk-1”=“pj-k pj-1” }

当此集合非空时 当j=0时 其他情况

若“p0 pk-1”=“pj-k pj-1”，即next[j] = k，则next[j+1] = ? ①若pk=pj，则有“p0 pk-1pk”=“pj-k pj-1pj” （0<k<j），如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。 ②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。

Kmp:从S的pos位置开始与T进行匹配，若S与T对应位置相等或T回到0位置时，S与T同时右移;否则T回到next[j]位置。

3、字符串的加密、解密： 1)Encrypt算法：

对字符串中的单个字符c的二进制形式进行操作，通过右移和与位运算等其分为两部分，存储在两个字符中。

2)Decrypt算法：

对字符串中的单个字符c的二进制形式进行操作，通过左移和与位运算等两个字符还原累加，得到原字符。 4.文本文件单词的检索与计数； 1）建立文件的实现思路是：

(1) 定义一个串变量； (2) 定义文本文件；

(3) 输入文件名，打开该文件；

(4) 循环读入文本行，写入文本文件，其过程如下：

while(不是文件输入结束){

读入一文本行至串变量；

串变量写入文件； 输入是否结束输入标志；｝

(5) 关闭文件。

2）给定单词计数的实现思路是：

(1) 输入要检索的文本文件名，打开相应的文件；