数据结构—串的详细解释（含KMP算法）

这篇具有很好参考价值的文章主要介绍了数据结构—串的详细解释（含KMP算法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.1串的定义

串：串是由零个或多个字符组成的有限序列，又叫字符串(其的存储结构包含顺序表存储、单链表存储的形式。)

一般记为s="a1a2a3....an"(n>=0)，其中，s是串的名称，用双引号(也可以使用单引号)括起来的字符序列是串的值，注意引号不是串的内容。ai(i<=i<=n)可以是字母、数字或者其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，定义中谈到"有限"是指长度为n是一个有限的数值。零个字符的串称为空串，它的长度为0，可以直接用两个双引号表示，也可以用其他的字符表示空串。所谓的序列说明串的相邻字符之间具有前驱和后继的关系。

（1）空格串，空格串是有长度的串内容为空格。

（2）子串与主串，串中任意个数的连续字符组成的子序列为该串的子串，包含子串的串即为主串.

子串在主串的位置就是子串第一个字符在主串的位置的序号。

1.2串的比较

串的比较实际上就是判断字母前后的ASCII码的大小。比较两个串相等时，必须是它们串的长度以及它们各个位置上的内容完全一致才为相等。

当串在比大小时，串中内容都相同但有一个串的长度比其大一点则长度大的就是比另一个串大，相反长度小的则比另一个串小了。

1.3串的抽象数据类型

串的一些操作函数（需要自己去书写）：

串（string）

DATA

串中元素仅由一个字符组成，相邻元素具有前驱和后继的关系

Operation

StrAssign（T，*chars）：生成一个其值等于字符串常量chars的串T

StrCopy（T，S）：串S存在，由串S复制得串T

ClearString（S）：将串S清空

StringEmpty（S）：若串为空则返回true，不为空则返回false

StringLength（S）：返回串S的元素个数，即串的长度

StrCompare（S，T）：若S>T，返回值>0,若S=T，返回0，若S<T，返回值<0

Concat（T，S1，S2）：用T存储S1和S2连接后的串

SubString（Sub，S，pos，len）：串S存在1<=pos<=Stringlength(s), 且 0<=len<=StringLength(S)-pos-1,用Sub返回串S第pos起长度为len的子串。

Index（S，T，pos）：用串S和T存在，T非空，若S中存在与T相同的串则返回它在pos后第一个出现的位置

Repalce（S，T，V）：用V替换主串S中所有出现与T相同的不重叠的子串

StrInsert（S，pos，T）：在串s的pos处插入子串T

StrDelete（S，pos，len）：删除串s的pos处长len的子串

（1）StrCopy函数

代码如下：（还可以将字符数组更改为string类型）

#include<iostream>
using namespace std;
#define Max 20
void StrCopy(char *T,char *S);

int main()
{
	char s[Max],T[Max];	
	cin>>s;
	cout<<"S:";
	cout<<s<<endl;
	cout<<"T:";
	StrCopy(T,s);
	cout<<T;
} 

void StrCopy(char *T,char *S)	//传递指针指向字符数组的首地址 
{
	int i;
	for(i=0;S[i]!='\0';i++)	//根据主串长度赋值给串T 
		T[i]=S[i];
	T[i]='\0';
}

#include<iostream>
using namespace std;
#define Max 20
void StrCopy(string &T,string &S);

int main()
{
	string s,T;	
	cin>>s;
	cout<<"S:";
	cout<<s<<endl;
	cout<<"T:";
	StrCopy(T,s);
	cout<<T;
} 

void StrCopy(string &T,string &S)	
{
	T=S;
}

运行结果如下图所示：数据结构—串的详细解释（含KMP算法）

（2）StrAssign()函数

代码如下：

#include<iostream>
using namespace std;
#define Max 20
StrAssign (string &T,char *s)
{
	T=s;
}

int main()
{
	string T;
	StrAssign(T,"love");
	cout<<"T:"<<T;
	return 0;
}

运行结果如下图所示：数据结构—串的详细解释（含KMP算法）

（3）ClearString()函数

代码：

#include<iostream>
using namespace std;
#define Max 20
void Clear(string &S)
{
	int i;
	for(i=0;S[i]!='\0';i++)
		S[i]='\0';
}

int main()
{
	string S;
	cin>>S;
	cout<<"S:"<<S<<endl;
	Clear(S);
	cout<<S;
	return 0;
}

运行结果如下图：数据结构—串的详细解释（含KMP算法）

（4）StringEmpty()函数

代码：

#include<iostream>
using namespace std;
#define Max 20
bool StrEmpty(string S)
{
	if(S[0]=='\0')
		return true;
	else
		return false;
}

int main()
{
	string S;
	cin>>S;
	cout<<"S:"<<S<<endl;
	if(StrEmpty(S))
		cout<<"S字符串为空！";
	else
		cout<<"S字符串不为空！"; 
	return 0;
}

运行结果如下：数据结构—串的详细解释（含KMP算法）

（5）StrLength()函数

代码：

#include<iostream>
using namespace std;
#define Max 20
int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

int main()
{
	string S;
	int n;
	cin>>S;
	cout<<"S:"<<S<<endl;
 	n=StrLength(S);
 	cout<<"S的长度为:"<<n;
	return 0;
}

运行结果如下：

数据结构—串的详细解释（含KMP算法）

（6）StrCompare()函数

代码：

#include<iostream>
using namespace std;
#define Max 20
int StrCompare(string S,string T)
{
	int i=0;
	while(S[i]!='\0'&&T[i]!='\0')
	{
		if(S[i]>T[i])
			return 1;
		else if(S[i]<T[i])
			return -1;
		i++;
	}
	if(S[i]!='\0')
		return 1;
	if(T[i]!='\0')
		return -1;
	if(T[i]=='\0'&&S[i]=='\0')
		return 0;
}

int main()
{
	string S,T;
	int n;
	cin>>S>>T;
	cout<<"S:"<<S<<endl;
	cout<<"T:"<<T<<endl;
	n=StrCompare(S,T);
	if(n>0)
		cout<<"S大于T."<<endl;
	else if(n==0)
		cout<<"S等于T."<<endl;
	else
		cout<<"S小于T."<<endl;
	return 0;
}

运行结果：
数据结构—串的详细解释（含KMP算法）

（7）Concat()函数

在string中有重载的运算符+表示串的连接所以直接使用即可，在字符数组中则用指针赋值的方法先找到一个串的尾部再让第二个串赋值给第一个串尾即可

代码：

#include<iostream>
using namespace std;
#define Max 20
void Concat(string &T,string S1,string S2)
{
	T=S1+S2;
}

int main()
{
	string S1,T,S2;
	cin>>S1>>S2;
	cout<<"S1:"<<S1<<endl;
	cout<<"S2:"<<S2<<endl;
	Concat(T,S1,S2);
	cout<<"T:"<<T;
	return 0;
}

#include<stdio.h>
#define Max 20
 
char * my_strcat(char * dest,char * src)  
 
{
 char *ret = dest;         //定义一个ret来保存dest的值；
 
 while(* dest!='\0')      //判断是否是第一个字符串数组的元素是否是末尾
 {                        
  dest++;              //使指向下一个元素
 }
 * dest = *src;           //将第二个数组的首元素赋给‘\0’
 while(* src != '\0')     //判断是否是第二个字符串数组的元素是否是末尾
 {
  * dest++ = *src++;    //将原来第二个数组中各元素赋给第一个数组
 
 }
  *src++ = '\0';       //在最后一个数组后面赋上‘\0’
 return ret; 
}
int main()
{
 char str1[Max]={"lo"};
 char str2[Max]={"ve"};
 
 my_strcat(str1,str2);    //调用my_stract函数
 
 printf("%s\n",str1);     
 
 return 0;
}

运行结果：

数据结构—串的详细解释（含KMP算法）

（8）SubString()函数

返回主串中pos位置处长度为len的子串到sub中，即将找到的位置加加赋值给sub【0.1.2......n】即可让sub最后一个值为、0意味着字符串结束

代码：

#include<iostream>
#include<cstdlib>
using namespace std;
void SubString(string &Sub,string S1,int pos,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		Sub[i]=S1[pos];
		pos++;
	}
	Sub[i+1]='\0';
}

int main()
{
	string S1,T;	//要保存子串首先要给T开空间 
	int pos,len;
	T="           ";
	cout<<"请输入字符串->";
	cin>>S1;
	cout<<"请输入位置和长度:";
	cin>>pos>>len; 
	cout<<"S1:"<<S1<<endl;
	SubString(T,S1,pos,len);
	cout<<"子串:"<<T;
	return 0;
}

运行结果：数据结构—串的详细解释（含KMP算法）

（9）Index()函数

代码如下：

先计算主串和子串的长度，计算成功后判断位置是否输入正确，正确后从主串pos位置处取出子串长度的字符，再与子串进行判断是否相等，相等则输出位置。

#include<iostream>
#include<cstdlib>
using namespace std;
void SubString(string &Sub,string S1,int pos,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		Sub[i]=S1[pos];
		pos++;
	}
}

int StrCompare(string S,string T)
{
	int i=0;
	while(S[i]!='\0'&&T[i]!='\0')
	{
		if(S[i]>T[i])
			return 1;
		else if(S[i]<T[i])
			return -1;
		i++;
	}
	if(S[i]!='\0')
		return 1;
	if(T[i]!='\0')
		return -1;
	if(T[i]=='\0'&&S[i]=='\0')
		return 0;
}

int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

int Index(string S,string T,int pos)
{
	int n,m,i;
	string sub;
	n=StrLength(S);
	m=StrLength(T);
	i=pos; 
	cout<<"子串中有"<<m<<"个数据\n";
	cout<<"请给sub开辟与子串相同的空间输入任意字符即可\n";
	cin>>sub;
	if(pos>0)
	{
		while(i<n-m+1)
		{	
			SubString(sub,S,i,m);
			if(StrCompare(sub,T)!=0)
				i++;
			else
				return i;	
		}	
	}	
	return 0;
} 
 
int main()
{
	string S1,T;	//要保存子串首先要给T开空间 
	int pos,i;
	cout<<"请输入字符串->";
	cin>>S1>>T;
	cout<<"请输入位置:";
	cin>>pos; 
	i=Index(S1,T,pos);
	if (i!=0)
		cout<<"找到子串的位置为:"<<i;
	else
		cout<<"没有找到子串!";
	return 0;
}

运行结果如下：数据结构—串的详细解释（含KMP算法）

（10）Replace()函数

代码如下所示：

不包含删除函数的替代函数，只可以替换与子串相同长度的串，有了删除函数则可以进行先删除后进行替换也就是插入某个位置即可。

#include<iostream>
using namespace std;
void SubString(string &Sub,string S1,int pos,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		Sub[i]=S1[pos];
		pos++;
	}
}

int StrCompare(string S,string T)
{
	int i=0;
	while(S[i]!='\0'&&T[i]!='\0')
	{
		if(S[i]>T[i])
			return 1;
		else if(S[i]<T[i])
			return -1;
		i++;
	}
	if(S[i]!='\0')
		return 1;
	if(T[i]!='\0')
		return -1;
	if(T[i]=='\0'&&S[i]=='\0')
		return 0;
}
 

int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

int Index(string S,string T,int pos)
{
	int n,m,i;
	string sub;
	n=StrLength(S);
	m=StrLength(T);
	i=pos; 
	cout<<"子串中有"<<m<<"个数据\n";
	cout<<"请给sub开辟与子串相同的空间输入任意字符即可\n";
	cin>>sub;
	if(pos>=0)
	{
		while(i<n-m+1)
		{	
			SubString(sub,S,i,m);
			if(StrCompare(sub,T)!=0)
				i++;
			else
				return i;	
		}	
	}	
	return 0;
} 

void Replace(string &S,string T,string V)
{
	int i,n;
	i=Index(S,T,0);
	n=StrLength(V);
	int j=i,k=0;
	while(k<n)
	{
		S[j]=V[k];
		j++;
		k++;		
	}
}

int getlen(string V,string T)
{
	int n=V.size();
	int m=T.size();
	return n-m;
}

int main()
{
	string S1,T,V;	//要保存子串首先要给T开空间 
	int pos,i;
	cout<<"请输入字符串->";
	cin>>S1;
	cout<<"请输入子串:";
	cin>>T;
	cout<<"请输入替代的串:";
	cin>>V; 
    if(n>0)
	{
		while(n--)
			S1+='1';
	}
	Replace(S1,T,V);
	cout<<S1;
	return 0;
}

#include <iostream>
using namespace std;

int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}
 

int StrCompare(string S,string T)
{
	int i=0;
	while(S[i]!='\0'&&T[i]!='\0')
	{
		if(S[i]>T[i])
			return 1;
		else if(S[i]<T[i])
			return -1;
		i++;
	}
	if(S[i]!='\0')
		return 1;
	if(T[i]!='\0')
		return -1;
	if(T[i]=='\0'&&S[i]=='\0')
		return 0;
}
 

void SubString(string &Sub,string S1,int pos,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		Sub[i]=S1[pos];
		pos++;
	}
}
 

int Index(string S,string T,int pos)
{
	int n,m,i;
	string sub;
	n=StrLength(S);
	m=StrLength(T);
	i=pos; 
	cout<<"子串中有"<<m<<"个数据\n";
	cout<<"请给sub开辟与子串相同的空间输入任意字符即可\n";
	cin>>sub;
	if(pos>=0)
	{
		while(i<n-m+1)
		{	
			SubString(sub,S,i,m);
			if(StrCompare(sub,T)!=0)
				i++;
			else
				return i;	
		}	
	}	
	return 0;
} 
 

void StrInsert(string &S,int pos,string T)
{
	int n,m,i=0;
	n=StrLength(T);
	for(int j=pos;j<pos+n;j++)
	{
		S[j+n]=S[j];
	}
	while(i<n)	
	{
		S[pos]=T[i];
		i++;
		pos++;
	}
} 
 

void StrDelete(string &S,int pos,int len)
{
	int i,m;
	m=StrLength(S);
	for(i=pos;i<m-len+1;i++)
	{
		S[i]=S[i+len];	
		S[i+len]=' ';		
	}
}
 

void Replace(string &S,string T,string V)
{
	int i,n,m;
	m=StrLength(T);
	i=Index(S,T,0);
	StrDelete(S,i,m);
	StrInsert(S,i,V);
}
 

int getlen(string V,string T)
{
	int n=V.size();
	int m=T.size();
	return n-m;
}

int main()
{
	string S1,T,V;	//要保存子串首先要给T开空间 
	int pos,i,n;
	cout<<"请输入字符串->";
	cin>>S1;
	cout<<"请输入子串:";
	cin>>T;
	cout<<"请输入替代的串:";
	cin>>V; 
	n=getlen(V,T);
	if(n>0)
	{
		while(n--)
			S1+='1';
	}
	Replace(S1,T,V);
	cout<<S1;
	return 0;
}

运行结果如下：

数据结构—串的详细解释（含KMP算法）

（11） StrInsert(S，pos，T）函数

该函数需要给string预留足够多的空间来保存T长度的后移要不然就相当于用子串将其替代了，相对如此可以使用字符数组来使用更简单一点。也可以直接给串开辟足够大的空间

代码如下：

#incldue<iostream>
using namespace std;
int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

void StrInsert(string &S,int pos,string T)
{
	int n,m,i=0;
	n=StrLength(T);
	for(int j=pos;j<pos+n;j++)    //后移目标存储的位置
	{
		S[j+n]=S[j];
	}
	while(i<n)	    //给目标位置赋值
	{
		S[pos]=T[i];
		i++;
		pos++;
	}
} 
 
int main()
{
	string S1,T;	//要保存子串首先要给T开空间 
	int pos;
	cout<<"请输入子串:";
	cin>>T;
	cout<<"子串长度为"<<StrLength(T)<<"请预留位置\n";
	cout<<"请输入字符串:";
	cin>>S1;
	cout<<"请输入要插入的位置:";
	cin>>pos;
	StrInsert(S1,pos,T);
	cout<<S1;
	return 0;
}

运行的结果如下所示：

数据结构—串的详细解释（含KMP算法）

（12）StrDelete(S,pos,len)的函数

计算S串的长度然后用长度减去要删除的长度+1为后续要前移的元素，然后将后面的元素进行前移操作，再将原来后面的元素置为空即可，字符串的做法与其类似只不过不用置空直接将长度减去要删除的长度即可。

数据结构—串的详细解释（含KMP算法）

代码如下：

#include<iostream>
using namespace std;
int StrLength(string S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

void StrDelete(string &S,int pos,int len)
{
	int i,m;
	m=StrLength(S);
	for(i=pos;i<m-len+1;i++)
	{
		S[i]=S[i+len];	
		S[i+len]=' ';	   //将后面元素置空
	}
}
 
int main()
{
	string S1;	
	int pos,len;
	cout<<"请输入字符串:";
	cin>>S1;
	cout<<"请按顺序输入删除位置与删除长度:";
	cin>>pos>>len;
	StrDelete(S1,pos,len);
	cout<<S1;
	return 0;
}

运行结果如图所示：

数据结构—串的详细解释（含KMP算法）

1.4朴素的模式匹配算法

子串的定位操作通常被称为串的模式匹配。

简单来说就是对主串的每一个字符作为子串的开头，要与匹配的字符进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配完成或者全部遍历完成为止。

我先把代码放在下面以及运行结果：

代码如下：

#include<iostream>
using namespace std;
#define Max 20
int StrLength(char *S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

int Index(char *S,char *T,int pos)
{
	int i=pos;
	int j=0,m,n;
	m=StrLength(S);
	n=StrLength(T);
	while(i<=m&&j<n)
	{
		if(S[i]==T[j])    //相同则同时进行后移
		{
			++i;
			++j;
		}
		else //不相同且未超过子串长度则返回主串下一个位置，子串置0
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j>=n)
		return i-n;    //返回在主串中的位置即主串匹配完成的位置减去子串长度
	else 
		return 0;
}

int main()
{
	char S[Max],T[Max];
	int pos,i;
	cout<<"请输入字符串:";
	cin>>S;
	cout<<"请输入要查找的子串:";
	cin>>T;
	cout<<"请输入要开始查找的位置:";
	cin>>pos;
	i=Index(S,T,pos);
	cout<<"返回的位置为:"<<i;
	return 0;
}

数据结构—串的详细解释（含KMP算法）

运算过程如下：

数据结构—串的详细解释（含KMP算法）

1.5KMP模式匹配算法

1.5.1匹配算法原理

数据结构—串的详细解释（含KMP算法）

按照朴素模式匹配算法，应该是如上图(2),(3),(4),(5),(6)。即主串S中当i=2、3、4、5、6时，首字符与子串T的首字符均不相等。因为子串中首字符a不与其子串后的任意一个元素相等所以只运行(1),(6)即可，因此我们要提高该算法的匹配能力则需要记录子串中是否存在相同的字符。KMP模式匹配算法就是为了让这没必要的回溯不发生。由上图可以看出j的大小取决于当前字符之前的串的前后缀的相似度。即可以用一个数组来保存其回溯的位置。

1.5.2next数组值的推导

具体如何推导出一个串的next的数组值呢？我们看看如下几个例子再进行总结。

数据结构—串的详细解释（含KMP算法）

如果前后缀的字符相同则next数组在原本的数值基础上+1，如果不相同则进行回溯操作直到找到相同的数值，然后令其next的数值+1等于当前next的值。

1.5.3KMP算法实现

代码如下所示：

#include<iostream>
using namespace std;
#define Max 20
int StrLength(char *S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

void get_next(char *T,int *next)
{
	int i,k;
	i=1;
	k=0;
	next[1]=0;
	while(i<StrLength(T))	//直到大于等于长度退出 
	{
		//k=0时是第一个字符所以先给其分配数值=1，相当于字符前现只有一个值 
		if(k==0||T[i]==T[k])	//如果相同则回溯时可以一个一个与前串相比 
		{
			++i;
			++k;
			next[i]=k;	//相同则加一即可 可理解为在子串中回溯的位置靠后一个 
		}
		else
			k=next[k];	//如果与当前的字符不同则可以在于前一个字符进行比较，如果相同则next的数组值+1 
	}
}

int Index(char *S,char *T,int pos)
{
	int i=pos;
	int j=1,m,n;
	m=StrLength(S);
	n=StrLength(T);
	int next[Max];
	get_next(T,next);
	while(i<=m&&j<n)
	{
		if(j==0||S[i]==T[j]) 
		{
			++i;
			++j;
		}
		else	//回溯到应该的位置 
			j=next[j];
	}
	if(j>=n)
		return i-n;
	else
		return 0;
}

int main()
{
	char S[Max],T[Max];
	int pos,i,next[Max];
	cout<<"请输入字符串:";
	cin>>S;
	cout<<"请输入要查找的子串:";
	cin>>T;
	cout<<"请输入要开始查找的位置:";
	cin>>pos;
	i=Index(S,T,pos);
	cout<<"返回的位置为:"<<i;
	return 0;
}

运行的结果如下图所示：数据结构—串的详细解释（含KMP算法）

1.5.4KMP算法改进

对next数组的寻找合适位置进行了改进，如果字符串中前缀中相同字符太多，则会减慢运行速度，因为next的值仍然会让其一个一个回溯一个已经不匹配的字符，因此我们要在其基础上进行改进。

代码如下所示：

#include<iostream>
using namespace std;
#define Max 20
int StrLength(char *S)
{
	int i=0;
	while(S[i]!='\0')
		i++;
	return i;
}

void get_nextval(char *T,int *nextval)
{
	int i,k;
	i=1;
	k=0;
	nextval[1]=0;
	while(i<StrLength(T))	//直到大于等于长度退出 
	{
		//k=0时是第一个字符所以先给其分配数值=1，相当于字符前现只有一个值 
		if(k==0||T[i]==T[k])	//如果相同则回溯时可以一个一个与前串相比 
		{
			++i;
			++k;
			if(T[i]!=T[k])	//如果串的字符不相等即以及回溯到了顶端时让其+1且赋给nextval 
				nextval[i]=k;
			else
				nextval[i]=nextval[k];	
		}
		else
			k=nextval[k];	//如果与当前的字符不同则可以在于前一个字符进行比较，如果相同则next的数组值+1 
	}
}

int Index(char *S,char *T,int pos)
{
	int i=pos;
	int j=1,m,n;
	m=StrLength(S);
	n=StrLength(T);
	int nextval[Max];
	get_nextval(T,nextval);
	while(i<=m&&j<n)
	{
		if(j==0||S[i]==T[j]) 
		{
			++i;
			++j;
		}
		else	//回溯到应该的位置 
			j=nextval[j];
	}
	if(j>=n)
		return i-n;
	else
		return 0;
}

int main()
{
	char S[Max],T[Max];
	int pos,i,next[Max];
	cout<<"请输入字符串:";
	cin>>S;
	cout<<"请输入要查找的子串:";
	cin>>T;
	cout<<"请输入要开始查找的位置:";
	cin>>pos;
	i=Index(S,T,pos);
	cout<<"返回的位置为:"<<i;
	return 0;
}

运行的结果如下图：

数据结构—串的详细解释（含KMP算法）