关键词:
串
串(string)是由零个或多个字符组成的有限序列。含零个字符的串称为空串,用Ø表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成"a1a2a3a4…“的形式,其中最外边的双引号(或单引号)不是串的内容,它们是串的标志,用于将串与标识符(如变量名等)加以区别。每个 a(1≤i≤n)代表一个字符,不同的机器和编程语言对合法字符(即允许使用的字符)有不同的规定。但在一般情况下,英文字母、数字(0,1,9)和常用的标点符号以及空格符等都是合法的字符。
两个串相等当且仅当这两个串的长度相等并且各对应位置上的字符都相同。一个串中任意个连续字符组成的序列称为该串的子串(substring),例如串”abcde"的子串有"a”、“ab”、"abc"和"abcd"等。为了表述清楚,在串
中空格字符用“□”符号表示,例如"a□□b"是一个长度为 4 的串,其中含有两
个空格字符。空串是不包含任何字符的串,其长度为 0,空串是任何串的
子串
顺序串代码实现
#include <iostream>
#include <stdio.h>
#define MaxSize 100
using namespace std;
typedef struct
///顺序串的定义
char data[MaxSize];
int length;
SqString;
void StrAssign(SqString &s,char cstr[])
///字符串常量赋值给串a
int i;
for(i = 0;cstr[i] != '\\0';i++)
s.data[i] = cstr[i];
s.length = i;
void StrCopy(SqString &s,SqString t)
///串的复制
for(int i= 0;i<t.length;i++)
s.data[i] = t.data[i];
s.length = t.length;
bool StrEqual(SqString s,SqString t)
///判断串是否相等
bool same = true;
if(s.length != t.length)
same = false;
else
for(int i = 0;i<s.length;i++)
if(s.data[i] != t.data[i])
same = false;
break;
return same;
int StrLength(SqString s)
///求串的长度
return s.length;
SqString Concat(SqString s,SqString t)
///连接两个串
SqString str;
int i;
str.length = s.length +t.length;
for(i = 0;i<s.length;i++)
str.data[i] = s.data[i];
for( i =0;i<t.length;i++)
str.data[s.length + i] =t.data[i];
return str;
SqString SubStr(SqString s,int i,int j)
///求子串
SqString str;
int k;
str.length = 0;
if(i<=0||i>s.length||j<0||i+j-1>s.length)
return str;
for(k = i-1;k<i+j-1;k++)
str.data[k-i+1] = s.data[k];
str.length = j;
return str;
SqString InsStr(SqString s1,int i,SqString s2)
///插入子串
int j;
SqString str;
str.length = 0;
if(i<=0 || i>s1.length+1)
return str;
for(j=0;j<i-1;j++)
str.data[j] = s1.data[j];
for(j = 0;j<s2.length;j++)
str.data[i+j-1] = s2.data[j];
for(j = i-1;j<s1.length;j++)
str.data[s2.length+j] = s1.data[j];
str.length = s1.length+s2.length;
return str;
SqString DelStr(SqString s,int i,int j)
///删除子串
int k;
SqString str;
str.length = 0;
if(i<=0||i>s.length||i+j>s.length+1)
return str;
for(k = 0;k<i-1;k++)
str.data[k] = s.data[k];
for( k =i+j-1;k<s.length;k++)
str.data[k-j] = s.data[k];
str.length = s.length -j;
return str;
SqString RepStr(SqString s,int i,int j,SqString t)
///替换子串
int k;
SqString str;
str.length = 0;
if(i<=0||i>s.length||i+j-1>s.length)
return str;
for(k = 0;k<i-1;k++)
str.data[k] = s.data[k];
for(k = 0;k<t.length;k++)
str.data[i+k-1] = t.data[k];
for(k = i+j-1;k<s.length;k++)
str.data[t.length+k-j] = s.data[k];
str.length = s.length-j+t.length;
return str;
void DispStr(SqString s)
///输出串
if(s.length >0)
for(int i = 0;i<s.length;i++)
printf("%c",s.data[i]);
printf("\\n");
int main()
SqString s,s1,s2,s3,s4;
printf("顺序串的基本运算如下:\\n");
printf("1-建立串s和串s1\\n");
StrAssign(s,"abcdefghijklmn");
StrAssign(s1,"123");
printf("2-输出串s:");DispStr(s);
printf("3-串s的长度:%d\\n",StrLength(s));
printf("4-在串s的第9个字符位置插入串s1而产生串s2\\n");
s2 = InsStr(s,9,s1);
printf("5-输出串s2:");DispStr(s2);
printf("6-删除串s的第2个字符开始的5个字符产生串s2\\n");
s2 =DelStr(s,2,3);
printf("7-输出串s2:");DispStr(s2);
printf("8-将串s第2个字符开始的5个字符替换成串s1而产生串s2\\n");
s2 = RepStr(s,2,5,s1);
printf("9-输出串s2");DispStr(s2);
printf("10-提取串s的第2个字符开始的10个字符而产生串s3");
s3 = SubStr(s,2,10);
printf("11-输出串s3:");DispStr(s3);
printf("12-将串s1和s2连接起来而产生串s4\\n");
s4 = Concat(s1,s2);
printf("13-输出串s4:");DispStr(s4);
return 1;
串的模式匹配
BF 算法
Brute-Force(暴力)简称为 BF 算法,也称简单匹配算法,采用穷举方法,其基本思路是从目标串s="s0 …sn-1"的第一个字符开始和模式串t=”t0…tm-1"中的第一个字符比较,若相等,则继续逐个比较后续字符;否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依此类推,若从模式串s的第i个字符开始,每个字符依次和目标串 t中的对应字符相等,则匹配成功,该算法返回位置 i(表示此时 i的第一个字符在5中出现的下标);否则,匹配失败,即t不是s的子串,算法返回-1(这里为了简便,均使用物理下标)。
代码实现
int BF(SqString s,SqString t)
///简单匹配算法
int i = 0,j = 0;
while(i<s.length&&j<t.length)
if(s.data[i] == t.data[j])
i++;
j++;
else
i = i-j+1;
j = 0;
if(j>=t.length)
return (i-t.length);
else
return -1;
KMP算法
Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。
KMP算法并不是很好理解,所以找了一篇解释KMP算法写的比较好的文章
数据结构KMP算法详解
代码实现
求next数组的代码
typedef struct
char data[MaxSize];
int length; //串长
SqString;
//SqString 是串的数据结构
//typedef重命名结构体变量,可以用SqString t定义一个结构体。
void GetNext(SqString t,int next[]) //由模式串t求出next值
int j,k;
j=0;k=-1;
next[0]=-1;//第一个字符前无字符串,给值-1
while (j<t.length-1)
//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
//所以最后一次经过while循环时j为t.length-2
if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时
j++;k++;
next[j]=k;
//对应字符匹配情况下,s与t指向同步后移
//通过字符串"aaaaab"求next数组过程想一下这一步的意义
//printf("(1) j=%d,k=%d,next[%d]=%d\\n",j,k,j,k);
else
k=next[k];
**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
//也表示该处字符不匹配时应该回溯到的字符的下标
//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
//printf("(2) k=%d\\n",k);
KMP算法代码
int KMPIndex(SqString s,SqString t) //KMP算法
int next[MaxSize],i=0,j=0;
GetNext(t,next);
while (i<s.length && j<t.length)
if (j==-1 || s.data[i]==t.data[j])
i++;j++; //i,j各增1
else j=next[j]; //i不变,j后退,现在知道为什么这样让子串回退了吧
if (j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
改进代码
求nextVal
void GetNextval(SqString t,int nextval[])
//由模式串t求出nextval值
int j=0,k=-1;
nextval[0]=-1;
while (j<t.length)
if (k==-1 || t.data[j]==t.data[k])
j++;k++;
if (t.data[j]!=t.data[k])
//这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
//为什么?因为没有这处if判断的话,此处代码是next[j]=k;
//next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
nextval[j]=k;
else
nextval[j]=nextval[k];
//这一个代码含义是不是呼之欲出了?
//此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
//用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
else k=nextval[k];
修正的KMP算法
int KMPIndex1(SqString s,SqString t)
//修正的KMP算法
//只是next换成了nextval
int nextval[MaxSize],i=0,j=0;
GetNextval(t,nextval);
while (i<s.length && j<t.length)
if (j==-1 || s.data[i]==t.data[j])
i++;j++;
else j=nextval[j];
if (j>=t.length)
return(i-t.length);
else
return(-1);
kmp算法(代码片段)
数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情
串串的模式匹配算法(子串查找)bf算法kmp算法(代码片段)
串的定长顺序存储#defineMAXSTRLEN255,//超出这个长度则超出部分被舍去,称为截断串的模式匹配:串的定义:0个或多个字符组成的有限序列S=‘a1a2a3…….an‘n=0时为空串串的顺序存储结构:字符数组,串的长度就是数组末尾‘ 查看详情
单模式串匹配----浅谈kmp算法(代码片段)
模式串匹配,顾名思义,就是看一个串是否在另一个串中出现,出现了几次,在哪个位置出现; p.s. 模式串是前者,并且,我们称后一个(也就是被匹配的串)为文本串; 在这篇博客的代码里,s1均为文本串,s2均为模... 查看详情
数据结构—串kmp模式匹配算法(代码片段)
数据结构—串串顺序串代码实现串的模式匹配BF算法代码实现KMP算法代码实现求next数组的代码KMP算法代码改进代码求nextVal修正的KMP算法串串(string)是由零个或多个字符组成的有限序列。含零个字符的串称为空串,用Ø表示。串中所... 查看详情
(原创)数据结构之利用kmp算法解决串的模式匹配问题(代码片段)
给定一个主串S(长度<=10^6)和一个模式T(长度<=10^5),要求在主串S中找出与模式T相匹配的子串,返回相匹配的子串中的第一个字符在主串S中出现的位置。输入格式:输入有两行:第一行是主串S;第二行是模... 查看详情
串的模式匹配算法之kmp(代码片段)
title:串的模式匹配算法之kmptags:数据结构与算法之美author:辰砂1.引言首先我们需要了解串的模式算法目的:确定主串中所含子串第一次出现的位置(定位);常见的算法种类:BF算法(又称古典的、经典的、朴素的、穷举的),KM... 查看详情
数据结构与算法之kmp算法(代码片段)
串的模式匹配算法子串(模式串)的定位操作通常称为串的模式匹配。这是串的一种重要操作,很多软件,若有“编辑”菜单项的话,则其中必有“查找”子菜单项。 串的顺序存储实现#include<stdio.h>#include<... 查看详情
kmp算法字符串匹配算法(代码片段)
简介字符串的模式匹配是对字符串的基本操作之一,广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域,如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻... 查看详情
kmp算法(代码片段)
...法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。原理匹配模式... 查看详情
kmp算法(next数组方法)(代码片段)
... intlength;;朴素的串匹配算法:设文本串text="ababcabcacbab",模式串为patten="abcac" 其匹配过程如下图所示。黑色线条代表匹配 查看详情
模式匹配----kmp算法(代码片段)
...,心却为她打着伞、在上篇中,我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯,即在匹配失败后,子串回溯到0,主串回... 查看详情
模式匹配----kmp算法(代码片段)
...,心却为她打着伞、在上篇中,我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯,即在匹配失败后,子串回溯到0,主串回... 查看详情
kmp算法(代码片段)
...设现在我们面临这样一个问题:有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找呢? 如果用暴力匹配的思路,并假设现在文本串S匹配到i位置,模式串P匹配到j位置,则有:如果当前字符匹配成功(... 查看详情
kmp算法(代码片段)
串的朴素模式匹配算法什么是字串匹配:在主串中找到与模式串相同的字串并返回其位置,如主串google、模式串gle,则结果为3算法思路:相当于拿着模式串和主串对齐,对比其第一个字符。不相等则模式串往... 查看详情
kmp算法应用举例(代码片段)
...重中之重A.题意:给T组数据,每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串,如果是输出最先匹配完成的位置,否则输出-1.做法:直接套用模板。把char改成int。kmp函数中在模式串遍历到结尾的时候return,若没... 查看详情
软考笔记(数据结构篇)————kmp算法(代码片段)
KMP算法主串P:abacbcabababbcbc模式串S:abacbca第一步:计算模式串S的前缀码规则:前后缀码必须一致且是最长,不能超过模式串本身。第二步:列好表格进行匹配,如下:比较开始:从模式串S[0]和主串P... 查看详情
kmp算法总结(代码片段)
【KMP简述】 主串长度为n,模式串长度为m,朴素的算法下,对于主串S的每一位S[i]都要往后扫描m个字符,所以时间复杂度为O(nm)。对于KMP算法,它的时间复杂度降到了O(m+n)。原理是用一个next数组预处理了主串的局部... 查看详情
实现顺序串的各种模式匹配算法(代码片段)
目的:掌握串的模式匹配算法(BF和KMP)设计内容:编写一个程序exp4-3.cpp,实现顺序串的各种模式匹配运算,并在此基础上完成以下功能:1、建立目标串s="abcabcdabcdeabcdefabcdefg"和模式串t="abcdeabcdefab";2、采用简单匹... 查看详情