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≤k0 但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
1.0 引言
美国国家半导体产品DP83640的独特性能，即100 Mb/s 下的同步以太网技术，可在用以太网连接的IEEE1588精密时 间协议（PTP）系统之间实现非常精确的同步。采用这种特 性，便可工作在要求的网络拓扑约束内，实现PTP应用达到 次纳秒级的主从同步精度。同时也能产生一个与主PTP时钟 锁定和校准的从结点时钟输出。
本应用注释首先提供了采用同步以太网模式测量主从结 点同步所得到的经验结果的总结。然后，提供了与同步以太 网模式相关的工作原理和拓扑限制有关的背景信息。接着讨 论了典型应用，通过经验数据清楚地解释了采用同步以太网 模式的潜在精度。本应用注释适用于下列产
2022-12-03 11:48:46
35KB
1
软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构软件架构
2022-12-03 00:13:43
3.16MB
1
考虑一个医学诊断问题，用快速生化检验筛查病人。根据下列似然函数，健
康者的检验返回结果接近0，受感染者的返回结果接近 1:
p(xw)=N(μ=0,o=0.3) p(x/w₂)=N(μ=1,σ=0.1)
假设平均1万个患者中有1人受感染，且误诊的代价如下:
(1)将健康者诊断为“感染者”:预计病人综合医疗费用为2万人民币。
(2) 将感染者诊断为“健康者”:预计由于误诊导致的医疗费用为 100 万人
民币。
根据下列准则，分析并确定决策规则:
(a) 最大似然,
(b)最大后验概率，(c)最小贝叶斯风险。讨论你的结果。
注意，可以使用 MATLAB 中的 solve 命令求解多项式的用符号表示的根，
用命令 subs 把符号表达式转换为数值。
2022-12-02 22:00:47
60KB
1
(1)冬1显示了4种装配零件的彩色冬像:螺母(nuts)、螺钉(screws)、支架(brackets)
和垫圈(washers)。请你设计一组特征(不超过4种)，能很好地把4种零件分开。
分析、讨论你的特征和背后的原理。
(2) 编写代码提取每种模式的上述4种特征，绘制每对特征的二维散点图(如.fl
vs.f2,f3 vs.f4，等)，讨论你的结果。
(3)计算原始空间中每一对样本之间的欧式距离。首先，你得把所有图像都转换
为同样大小,比如 32x32 彩色像素(提示:在 MATLAB 中,可使用函数 imresize)。
把距离组成30x30 的矩阵进行显示(提示:在 MATLAB中,可使用承数 imagesc)。
在一维特征空间中，重复上述过程。比较两种距离矩阵，在原始图像空间中和特征
=====================================================================================================================================================
2022-12-02 21:59:03
276KB
1
【S7-1200】CPU的启动模式
启动模式
S7-1200 CPU 通电后，它在开始执行循环用户程序之前首先执行启动程序。 CPU 支持以下组态选项：
1 不重新启动（保持为 STOP 模式）
2 暖启动 – RUN 模式（主要设置）
3 暖启动 – 断电前的模式（系统默认）
启动模式设置
2022-12-02 19:28:10
374KB
1
主要为大家详细介绍了vue实现滑动切换效果，仅在手机模式下可用，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
2022-12-02 16:55:57
50KB
1