- 浏览: 1465723 次
- 性别:
- 来自: 郑州
文章分类
最新评论
-
getelephantbyid:
make 无法通过.....
php-5.3,php-5.4的thttpd2.25b补丁,及编译方法 -
getelephantbyid:
patch -p1 ../php-5.4.7_thttpd-2 ...
php-5.3,php-5.4的thttpd2.25b补丁,及编译方法 -
zander:
zander 写道c 语言是静态类型语言还是动态类型语言阅读理 ...
什么是动态语言和静态语言? -
zander:
c 语言是静态类型语言还是动态类型语言
什么是动态语言和静态语言? -
lunajiayou:
很有道理,赞一个
跟着苍蝇会找到厕所,跟着蜜蜂会找到花朵
KMP 字符串模式匹配详解
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算 法。可以证明它的时间复杂度为O(m+n).。
int Index_BF ( char S [ ], char T [ ], int pos )
{
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
else
{
i ++; j = 0; // 重新开始新的一轮匹配
if ( T[j] == '\0')
else
如:T=”abCabCad” 则 next[6]=-1,因 T[3]=T[6]
下标
|
0
|
1
|
2
|
3
|
4
|
T
|
a
|
b
|
c
|
a
|
c
|
next
|
-1
|
0
|
0
|
-1
|
1
|
下标
|
0
|
1
|
2
|
3
|
4
|
T
|
a
|
b
|
c
|
a
|
b
|
next
|
-1
|
0
|
0
|
-1
|
0
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
T
|
a
|
b
|
a
|
b
|
c
|
a
|
a
|
b
|
c
|
next
|
-1
|
0
|
-1
|
0
|
2
|
-1
|
1
|
0
|
2
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
T
|
a
|
b
|
C
|
a
|
b
|
C
|
a
|
d
|
next
|
-1
|
0
|
0
|
-1
|
0
|
0
|
-1
|
4
|
next[5]= 0 根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
T
|
a
|
d
|
C
|
a
|
d
|
C
|
a
|
d
|
next
|
-1
|
0
|
0
|
-1
|
0
|
0
|
-1
|
0
|
void get_nextval(const char *T, int next[])
{
int j = 0, k = -1;
next[0] = -1;
while ( T[j/*+1*/] != '\0' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
else
k = next[k];
void getNext(const char* pattern,int next[])
{
next[0]= -1;
int k=-1,j=0;
while(pattern[j] != '\0')
{
if(k!= -1 && pattern[k]!= pattern[j] )
k=next[k];
++j;++k;
if(pattern[k]== pattern[j])
next[j]=next[k];
else
next[j]=k;
}
}
#include <iostream.h>
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
int len=0;
const char * c=Pattern;
{
}
int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
else
{
j=0;
++i;
}
}
if(Pattern[j]=='\0')
else
return -1;
</spa
发表评论
-
使用strongswan建立基于ikev2 eap-mschapv2的ipsec服务器
2017-04-17 23:14 3197sudo apt-get install strongsw ... -
使用strongswan/xl2tpd建立ipsec/l2tp服务器
2017-04-17 22:32 6155sudo apt-get install strongsw ... -
SecureFX中文件名乱码的解决
2014-08-28 03:23 3345原始贴子:https://forums.vandyke.c ... -
为Linux编译atheros ar1111(设备ID:168c:0037,AW-NB100H – AR5B225 Atheros half size)网卡驱动
2012-07-15 22:57 4588买了个zotac h61itx-a-e wifi主板,从zot ... -
PHY管理接口(MDIO)
2012-01-17 17:01 4214对吉比特以太网而言,串行通信总线称为管理数据输入输出 (MDI ... -
理解ipsec身份标识和认证选项
2012-01-11 15:42 6862This article is part of the Ide ... -
netfiletr和iptables的状态和连接跟踪机制
2012-01-11 15:38 3339Como se lleva a cabo el rastreo ... -
编译安装iw
2011-11-09 13:31 2372ubuntu安装build-essentials libnl- ... -
从ip addr add和ifconfig的区别看linux网卡ip地址的结构
2011-09-24 13:06 1668转至:http://blog.csdn.net/dog25 ... -
DLNA中的UPnP技术浅析
2011-09-22 18:39 5067说到DLNA,UPn ... -
Linux 用户态与内核态的交互——netlink 篇
2011-09-19 01:39 3509转至:http://bbs.chinaunix.net/thr ... -
netlink与rtnetlink(二)
2011-09-19 01:36 15951转至:http://blogold.chinaunix.net ... -
netlink和rtnetlink(一)
2011-09-19 01:35 5220转到:http://blogold.chinaunix.net ... -
Linux——Netlink
2011-09-19 01:24 9646转载:http://blog.csdn.net/firo_ba ... -
linux notification chains
2011-08-13 00:26 1049linux内核由各个不同的子系统构成,比如网络子系统、存储 ... -
内核中的notification chain浅析
2011-08-13 00:25 1373内核中的很多子系统都是联系很紧密的,因此有可能某个子系统的某些 ... -
Linux Notification chains
2011-08-13 00:24 2842Notifier是Linux 中提供一种在内核子系统 中共 ... -
printk 使用方法
2011-08-12 22:28 9877内核通过 printk() 输出的信息具有日志级别,日志级 ... -
WEXT/mac80211/nl80211/cfg80211
2011-07-29 02:32 11247Wireless-Extensions--旧的无 ... -
fedora上wpa_supplicant上网配置
2011-07-29 01:28 35331,vi /etc/sysconfig/wpa_supplic ...
相关推荐
KMP 算法详解 KMP 算法是字符串模式匹配的一种高效算法,解决了字符串中模式匹配的问题。该算法可以在 O(m+n) 的时间复杂度内完成字符串模式匹配。 简单匹配算法 简单匹配算法的思想是直截了当的,将主串 S 中...
KMP算法详解 KMP算法详解 KMP算法详解
### KMP算法详解 #### 一、KMP算法概述 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt三位计算机科学家共同提出。该算法主要用于解决在主...
"kmp算法详解" KMP 字符串模式匹配算法是高效的字符串匹配算法,时间复杂度为 O(m+n),其中 m 和 n 分别是主串和模式串的长度。KMP 算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。 KMP 算法的...
### KMP算法详解:原理与应用 #### 引言 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald E. Knuth、James H. Morris以及Vaughan Pratt三位计算机科学家共同提出。相较于传统的模式...
### 模式匹配的KMP算法详解 #### 一、KMP算法背景及传统模式匹配算法 KMP算法,即Knuth-Morris-Pratt算法,是由Donald E. Knuth、James H. Morris和Vaughan R. Pratt三位计算机科学家在1977年共同提出的一种高效的...
严蔚敏数据结构kmp算法详解PPT学习教案.pptx 本资源摘要信息将对严蔚敏数据结构kmp算法的学习教案进行详细的讲解和分析。KMP算法是字符串匹配算法中的一种重要算法,它可以高效地进行字符串匹配。 首先,我们需要...
### 字符串模式匹配KMP算法详解 #### 一、引言 在计算机科学领域,字符串模式匹配是一项基本且重要的任务。它涉及到在一个较大的文本字符串(通常称为“主串”或“目标串”)中寻找一个较小的字符串(称为“模式串...
严蔚敏-数据结构-kmp算法详解.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
《KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种在字符串中查找子串出现位置的高效算法,由Donald Knuth、James H. Morris和 Vaughan Pratt共同提出。该算法避免了在匹配过程中对已匹配部分的重新比较,显著...
"KMP算法详解" 一、KMP字符串模式匹配算法 KMP字符串模式匹配算法是一种高效的字符串模式匹配算法,能够在一个字符串中快速地定位另一个字符串。该算法的时间复杂度为O(m+n),远远优于简单匹配算法的时间复杂度O(m...
KMP算法详解.mhtml
【KMP算法详解】 KMP(Knuth-Morris-Pratt)算法是一种高效地进行字符串模式匹配的算法,由D.E.Knuth、J.H.Morris和V.R.Pratt三位学者独立提出。它解决了在主串(S)中查找模式串(T)出现的位置问题,避免了在匹配...
KMP、Mancher和扩展KMP算法详解,但是其中的参考代码有一点小错误,请自行参考网络
相比于简单的暴力匹配算法,KMP算法显著提高了性能,避免了不必要的字符回溯。它的核心在于构造一个模式函数next,也称为部分匹配表,用于存储模式串中每个位置的最长前缀和后缀的公共长度。 简单匹配算法,也称为...
本文介绍了KMP算法的原理和基本实现方法,附带算法模板的代码和详解。如想了解更多内容,欢迎关注微信公众号:信息学竞赛从入门到巅峰。
KMP算法的核心在于构建一个称为“部分匹配表”或“next数组”,用于存储模式串中每个位置的前缀和后缀的最大公共长度。 在构建next数组的过程中,我们需要遵循以下两个条件: 1. 当比较到某个位置时,如果模式串的...