首页 > 其他分享 >【理解串】

【理解串】

时间:2024-07-11 21:58:45浏览次数:13  
标签:子串 int S1 ++ length 理解 str

目录

一、串的基本概念

串:即字符串(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、算法思想

  1. 先将主串中与模式串长度相同的子串找出来,挨个与模式串对比,当所比子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串;
  2. 若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要进行(n-m+1)*m次,最坏时间复杂度为:O(mn);
  3. 最坏情况:每个子串的前m-1个字符都与模式串匹配,只有第m个字符不匹配;
  4. 比较好的情况:每个子串的第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数组

  1. 串的前缀:包含第一个字符,且不包含最后一个字符的子串;
  2. 串的后缀:包含最后一个字符,且不包含第一个字符的子串;
  3. 当第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

相关文章

  • C语言大端存储和小端存储到底有什么区别? 结尾详细题目加深理解
    一.为什么有大端小端模式?        大端模式(Big-endian)和小端模式(Little-endian)是计算机科学中数据存储的一种方式,它们指的是多字节数据类型(如整数、浮点数等)在内存中的字节序(byteorder)。这两种模式的主要区别在于数据的最高有效字节(MSB)和最低有效字节(LSB)的存储位置。......
  • 理解 Linux 文件权限(2)& vim编辑器
    1、如何理解文件权限1)查看文件• 想要理解文件权限,需要先从查看文件入手•使用ls–l命令查看Linux系统上的文件、目录和设备的权限①对象的类型②文件属性③目录/链接个数④所有者(owner)⑤组(group)⑥文件大小⑦最后修改的日期⑧文件名其中:• ①代表了对象的类型:......
  • 深入理解 CompletableFuture 的底层原理
    引言在现代Java编程中,异步编程变得越来越重要。为了实现高效和非阻塞的代码,Java8引入了CompletableFuture,一个用于构建异步应用程序的强大工具。本文将详细探讨CompletableFuture的底层原理,展示其工作机制,并通过代码示例说明如何在实际应用中使用它。异步编程的背景......
  • Java中的继承:深入理解与实践
    引言在面向对象编程中,继承是一个核心概念,它允许我们定义一种层次结构的类,其中子类可以继承父类的属性和方法。Java作为一种广泛使用的面向对象编程语言,自然也支持继承机制。本文将深入探讨Java中的继承,包括其定义、特点、使用场景以及实践中的注意事项。继承的定义在Java......
  • 阿里开源语音理解和语音生成大模型FunAudioLLM
       近年来,人工智能(AI)的进步极大地改变了人类与机器的互动方式,例如GPT-4o和Gemin-1.5等。这种转变在语音处理领域尤为明显,其中高精度的语音识别、情绪识别和语音生成等能力为更直观、更类人的交互铺平了道路。阿里开源大模型FunAudioLLM,一个创新的框架,旨在促进人类与大型......
  • 观《深入理解C#》有感---泛型五种约束
    一、引用类型约束classSample<T>whereT:class类型实参可以是:任何类: Sample<string>接口: Sample<IDisposable>数组: Sample<int[]>委托: Sample<Action>二、值类型约束classSample<T>whereT:struct类型实参可以是:值类型: Sample<int>枚举: Sample&l......
  • 观《深入理解C#有感》--- 排序搜索
    关于在无序列表中,找到所需数据的五种写法classProgram{classProduct{publicstringname;publicintprice;publicoverridestringToString(){returnname;......
  • 理解 OpenAI 的 CLIP 模型
    来源:https://medium.com/@paluchasz/understanding-openais-clip-model-6b52bade3fa3CLIP是由OpenAI在2021年发布的,自那时起已成为许多多模态AI系统中的基础构件之一。本文深入探讨了CLIP是什么、它是如何工作的、如何使用以及其实现方式。引言CLIP,即ContrastiveLan......
  • 对Stream函数式编程的理解
    什么是StreamStream被翻译为流,它的工作过程像将一瓶水导入有很多过滤阀的管道一样,水每经过一个过滤阀,便被操作一次,比如过滤,转换等,最后管道的另外一头有一个容器负责接收剩下的水。示意图如下:首先通过source产生流,然后依次通过一些中间操作,比如过滤,转换,限制等,最后结束对流的操......
  • 深入理解Java中的并发编程
    深入理解Java中的并发编程大家好,我是微赚淘客系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!并发编程是Java开发中的一个重要领域,通过并发编程,可以提高程序的执行效率和资源利用率。本文将深入探讨Java中的并发编程,包括线程的创建、同步机制、并发集合、线程池和并发工具类......