KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一.简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。）
三. 怎么求串的模式值next[n]
定义：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
1. next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
2. next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
3. next[n]= k >0 但k
#include
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。
int len=0;
const char * c=Pattern;
while(*c++!='\0')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next=new int[len+1];
get_nextval(Pattern,next);//求Pattern的next函数值
int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}//while
delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}
int main()//abCabCad
{
char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";
char*pattern="adCadCad";
//getNext(pattern,n);
//get_nextval(pattern,n);
cout<
2022-12-03 21:12:51
418KB
1
Java Emoji Converter（Emoji表情转换工具）
Emoji转换工具，适合各种规格客户端生成的Emoji字符串转换成另外一种格式。
一种在每种类型之间转换表情符号字符串的工具，例如软银行表情符号，unicode表情符号，别名表情符号，html表情符号。
将软银行表情符号转换为unicode时，我们使用以下文件： :
快速入门快速入门
将此添加到您的maven pom文件中（将以下内容加入您的maven的pom文件中）：
< dependency>
< groupId>com.github.binarywang
< artifac
2022-12-03 12:47:24
57KB
1
如果输入的字符串是这个样子"AA BB CC12 01 0D 00 34 38 34 35 3230 41 35 3346 37 30 2C 00 00 00
2022-12-01 23:13:25
38KB
1
解码器-aaEncode
这是aaEncoded字符串的解码器。 我希望这对外面的人有用。 aaEncode最初是由@hasegawayosuke制造的-utf-8.jp/public/aaencode.html
2022-11-29 19:24:21
2KB
1
linxlAddress
将一个包含姓名、地址和手机/电话号码的字符串拆分开来。
base
[removed][removed]
[removed]
console.log(linxlAddress('18300000000赵三广东广州天河区林和中路11号'))
[removed]
npm
npm install linxladdress --save
import linxlAddress from 'linxladdress';
console.log(linxlAddress('18300000000赵三广东广州天河区林和中路11号'))
Licens
2022-11-29 15:10:01
23KB
1
比较两个字符串的相似度，利用Levenshein算法计算出两个字符串的最小编辑距离，根据最小编辑距离得出相似度，例如： 字符串1:1234 字符串2:51234，则他们的相似度为：4/5。
2022-11-28 18:05:56
234KB
1
主要介绍了golang实现unicode转换为字符串string的方法,实例分析了Go语言编码转换的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
2022-11-27 12:32:35
26KB
1