目录
一、串的基本概念
串:即字符串(string),是由零个或多个字符组成的有限序列,一般记为S = “a1a2a3a4...an”(n>=0)
。其中,S是串名,双引号’'括起来的字符序列是串的值,a可以是字母、数字或其他字符,串中字符的个数n称为串的长度,当n=0时,称串为空串。
注意:单引号里只能放一个字符,双引号中可以放字符串,两个占用空间也有区别,示例:
#include<iostream>
using namespace std;
int main() {
cout << "\'s\'的长度为:" << sizeof('s') << endl;
cout << "\"s\"的长度为:" << sizeof("s") << endl;
return 0;
}
运行结果如下:
因为"a"字符串结尾有一个’\0’字符,表示字符串结束,它也会占一个字节,而字符’a’只占一个字节。
子串:串中任意连续的字符组成的子序列;
主串:包含子串的串。
字符在主串中的位置:字符在串中的序号;
子串在主串中的位置:子串的首字符在主串中的位置。
串是一种特殊的线性表,数据元素之间呈线性关系,串的数据对象限定为字符集(中文字符、英文字符、数字字符、标点字符等)。
二、串的基本操作及实现
#include<iostream>
#define MaxSize 100
using namespace std;
//定长字符串
struct staiticString{
char str[MaxSize + 1];//为什么要+1
int length;//字符串长度
};
struct variableString{
char* str;
int length;
};
//字符串的基本操作
//串赋值
bool stringAssign(variableString& S, char* ch) {
delete S.str;
int length = 0;
char* c = ch;
while (*c != '\0')
{
length++;
c++;
}
if (length == 0) {
S.str = nullptr;
S.length = 0;
return true;
}
else {
S.str = new char[length + 1];
if (S.str == nullptr) {
return false;
}
else {
c = ch;
for (int i = 0; i <= length; i++,++c) {
S.str[i] = *c;
}
S.length = length;
return true;
}
}
}
//获取字符串长度
int GetLength(variableString S) {
return S.length;
}
//字符串比较
int stringCompare(variableString S1, variableString S2){
for (int i = 0; i < S1.length && i < S2.length; ++i) {
if (S1.str[i] != S2.str[i]) {
return S1.str[i] - S2.str[i];
}
}
//扫描过的所有字符都相同,则长度长的串更大
return S1.length - S2.length;
}
//连接串,将串S1和串S2连接起来,并将连接结果返回到result
bool stringContact(variableString &result, variableString &S1, variableString S2) {
delete result.str;
result.str = nullptr;
result.str = new char[S1.length + S2.length + 1];
if (result.str == nullptr) {
cerr << "Memory is not enough!" << endl;
return false;
}
//将S1的内容先放到result里
int i = 0;
while (i<S1.length) {
result.str[i] = S1.str[i];
i++;
}
//再把S2的内容放到紧接着S1内容的后面
int j = 0;
while (j<S2.length) {
result.str[i + j] = S2.str[j];
j++;
}
result.length = S1.length + S2.length;
return true;
}
//求子串,其中from为子串的起始位置,length为子串的长度
bool subString(variableString &reslut, variableString S1,int from, int length) {
//判断给定参数的合法性
if (from<0||from>S1.length||length<0||length>S1.length-from) {
cerr << "Parameters are wrong" << endl;
return false;
}
delete reslut.str;
reslut.str = nullptr;
if (length ==0) {
reslut.str = nullptr;
reslut.length = 0;
return true;
}
else {
reslut.str = new char[length + 1];
int i = from;
int j = 0;
while (i<from+length)
{
reslut.str[j++] = S1.str[i++];
}
reslut.str[j] = '\0';
reslut.length = length;
return true;
}
}
//清空串
bool clearString(variableString &S) {
delete S.str;
S.str = nullptr;
S.length = 0;
return true;
}
int main() {
variableString S1{};
char ch[MaxSize] = {'h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd', '!', '\0'};
//调用串赋值
stringAssign(S1,ch);
for (int i = 0; i < S1.length + 1; ++i) {
cout << S1.str[i];
}
cout << endl;
variableString S2{};
//S2.str = ch;
//S2.length = S1.length;
char ch1[MaxSize] = { 'h','e','l','l','o','\0'};
stringAssign(S2,ch);
//调用串比较
if (stringCompare(S1, S2) == 0) {
cout << "S1 equals S2" << endl;
}else if(stringCompare(S1,S2)>0){
cout << "S1 is bigger than S2" << endl;
}
else {
cout << "S1 is smaller than S2" << endl;
}
//串连接
variableString result1{};
stringContact(result1,S1,S2);
while (*result1.str != '\0')
{
cout << *result1.str++;
}
cout << endl;
//求子串
variableString result2{};
subString(result2,S1,1,8);
while (*result2.str != 0)
{
cout << *result2.str++;
}
cout << endl;
if (clearString(S1)) {
cout << "S1 has been cleared!" << endl;
}
return 0;
}
三、串的存储实现
3.1、静态数组实现
#define MaxSize 100
typedef struct staticString{
char ch[MaxSize];
int length;
};
3.2、动态数组实现
typedef struct variableString{
char *ch;
int length;
};
四、串的朴素模式匹配
串的模式匹配:
在主串中找到与模式串相同的子串,并返回其所在主串中的位置。
4.1、算法思想
- 先将主串中与模式串长度相同的子串找出来,挨个与模式串对比,当所比子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串;
- 若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要进行(n-m+1)*m次,最坏时间复杂度为:O(mn);
- 最坏情况:每个子串的前m-1个字符都与模式串匹配,只有第m个字符不匹配;
- 比较好的情况:每个子串的第1个字符就与模式串匹配。
4.2、代码实现
//S为主串,cs为模式串(子串)
int Index(string S, string cs){
int k = 1;
int i = k, j = 1;
while(i<=S.length && j<= cs.length){
if(S.str[i] == cs.str[j]){
++i, ++j;
}else{
k++,i=k,j+1;
}
}
if(j>cs.length){
return k;
else
return 0;
}
或者不用k的方法:
int Index(string S, string cs){
int i=0;//扫描主串
int j=0;//扫描模式串
while(i<S.length && j<cs.length){
if(S.str[i] == cs.str[i]){
++i;
++j;//继续比较后续字符
}else{
i = i-j + 1;//指针后退,重新开始匹配
j = 1;
}
}
if(j>cs.length)
return i-cs.length;
else return -1;
}
匹配成功的最好时间复杂度为:O(m);
匹配失败的最好时间复杂度为:O(n);
最坏时间复杂度为:O(mn);
五、KMP算法
5.1、算法思想
朴素模式串匹配算法的缺点:当某些子串与模式串部分匹配时,主串的扫描指针i经常回溯,导致时间开销增加;
KMP算法:当子串和模式不匹配时,主串指针不回溯,模式串指针j=next[j],算法平均时间复杂度:O(m+n)。
5.2、求模式串的next数组
- 串的前缀:包含第一个字符,且不包含最后一个字符的子串;
- 串的后缀:包含最后一个字符,且不包含第一个字符的子串;
- 当第i个字符匹配失败时,由前1~j-i个字符组成的串记为s,next[i]=s的最长前后缀长度+1,特别地:规定next[1]=0;
5.2、代码实现
//获取next数组
void getNext(SString SS, int next[]){
int i=1, j=0;
next[1]=0;
while(i<SS.length){
if(j==0||SS.str[1]==SS.str[j]{
++i,++j;
next[i]=j;
}else{
j=next[j];
}
}
}
//KMP算法,求主串中模式串的位序,没有则返回0
int Index_KMP(string S, string cs){
int i=1,j=1;
int next[cs.length+1];
getNext(cs,next);
while(i<=S.length || j<=cs.length){
if(j==0 || S.str[i] == cs.str[j]){
++i,++j;
}else{
j=next[j];
}
}
if(j>cs.length)
return i-cs.length;
else return 0;
}
int main(){
SString S={"ababcabcd", 9};
SString T={"bcd", 3};
printf("%d ", Index_KPM(S, T)); //输出9
}
KMP算法的进一步优化,改进next数组:
void getNextval(SString T, int nextval[]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0 || T.ch[i]==T.ch[j]){
++i; ++j;
if(T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}else
j=nextval[j];
}
}
标签:子串,int,S1,++,length,理解,str
From: https://blog.csdn.net/Pumpkin_O/article/details/140357209