算法小课堂（七）字符串

拼搏现实的明天。 2024-04-17 11:44 36阅读 0赞

## 一、概念 ##

### 1.1相关概念 ###

> 0C++中有两种字符串表示形式：C风格字符串和string类类型。
> 
> C风格字符串是
> 
>  *  字符数组使用null字符\\0终止的一维字符数组，
>  *  字符指针是一个指针变量，里面存放一个字符的地址
> 
> 而string类处理起字符串来会方便很多，完全可以代替C语言中的字符数组或字符串指针。
> 
> 使用string类需要文件包含： \#include <string>

### 1.2字符串的构造方法 ###

>  *  string s; //空串
>  *  string s=“nefuer”;//利用常量字符串构造字符串
>  *  string t = s;//利用已有的字符串对象赋值
>  *  string (3, ‘a’);//”aaa” string (“china”,1,3);//”hin”
>  *  string str3 = s+ t;

### 1.3字符串的基本操作 ###

#### 1.3.1输入 ####

C++中的输入大致有6种方法：cin，cin.get(),cin.getline(),gets(),getchar()

> **cin**  
> 用法一：最常用的方法，接收一个字符串，无论是string还是char a\[10\],都是一样，但是遇到“空格”,“TAB”,"回车"都结束。
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	string a, b;
>     	cin >> a >> b;
>     	cout << a << endl;
>     	cout << b << endl;
>     	return 0;
>     }

> **cin.get()**
> 
> 用法一：cin.get(字符变量名)可以用来接收字符
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	char ch;
>     	ch = cin.get();//或者是cin.get(ch);
>     	cout << ch;
>     	return 0;
>     }
> 
> 用法二：cin.get(字符数组名，接收字符个数)，用来接收一行字符串（可以接收空格），这个最大的用途是可以定量的接收字符的个数（但是要注意，如果定义的数组的个数是20，则实际上最大接收19个字符（可以小于19），还要加上'\\0'）
> 
> 这个方法只能正针对于是字符数组，不能使用string来输入。
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	char a[20];
>     	//string a;报错
>     	cin.get(a, 20);
>     	cout << a;
>     	return 0;
>     }

> **cin.getline()**  
> 可以接收空格，并且输出。浅显的用法其实和cin.get()差不多。（也不能使用string来进行输入）
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	char a[20];
>     	cin.getline(a, 20);
>     	cout << a;
>     	return 0;
>     }
> 
> 更加深层的用法其实就是cin.getline()的原型，这个函数本来有三个参数，分别是字符串的位置，接受个数，结束字符。  
> 如果将例子中cin.getline()改为cin.getline(m,5,'a');当输入jlkjkljkl时输出jklj，输入jkaljkljkl时，输出jk  
> 当用在多维数组中的时候，也可以用cin.getline(m\[i\],20)之类的用法：  
> 
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     
>     int main ()
>     {
>         char m[3][20];
>         for(int i=0;i<3;i++){
>             cout<<"\n请输入第"<<i+1<<"个字符串："<<endl;
>             cin.getline(m[i],20);
>         }
>         cout<<endl;
>         for(int j=0;j<3;j++)
>             cout<<"输出m["<<j<<"]的值:"<<m[j]<<endl;
>         return 0;
>     }

> **getline()**  
> 接收一个字符串，可以接收空格并输出，不过要包含\#include<string>  
> 这也就弥补了之前cin.getline()和cin.get（）的不能读取string的一个小的弊端  
> 这里还要将这个写法稍微改正一下getline(cin,字符串数组名);
> 
> 用法一：一行，默认换行符结束
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	string s;
>     	getline(cin,s);
>     	cout << s;
>     	return 0;
>     }
> 
> 用法二：//一行或者多行，以第三个参数结束
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	string s;
>     	getline(cin,s,'.');
>     	cout << s;
>     	return 0;
>     }

> **gets（)**  
> 接收一个字符串，可以接收空格并且输出，需要包含\#include<string>  
> 但是这个函数有些奇葩的是，这个函数必须要包含头文件string，但是这个函数却不能直接对变量string来进行赋值。
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	char s[10];
>     	gets_s(s);
>     	cout << s;
>     	return 0;
>     }
> 
> ![c78c8fe0510340feb184d92c2f3324b4.png][]
> 
> 这个函数不安全

> **getchar（）**  
> 获取单个字符,需要包含\#include<string>。  
> 这个函数尽量少用
> 
>     #include<iostream>
>     #include<string>
>     using namespace std;
>     int main()
>     {
>     	char ch;
>     	ch = getchar();
>     	cout << ch;
>     	return 0;
>     }
> 
> 适合用来吃回车

#### 1.3.2输出 ####

> **setw()函数**
> 
> C++中的setw()函数是在输出操作中使用的字段宽度设置，此函数的作用是：设置输出的域宽，n表示字段宽度。
> 
> **当后面紧跟着的输出字段长度小于n的时候，在该字段前面用空格补齐；当输出字段长度大于n时，全部整体输出。**
> 
> 包含在[头文件][Link 1]为**\#include <iomanip>**中，其中io代表输入输出，manip是manipulator（操纵器）的缩写iomanip的作用
> 
>     #include <iostream>
>     using namespace std;
>     
>     #include <iomanip>
>     
>     
>     int main()
>     {
>         cout << 123456789 << endl;
>         cout << setw(2) << 123 << setw(7) << 456789 << endl;
>         return 0;
>     }
> 
> ![3c357cb77df643fdac361ca882f69e07.png][]
> 
> 其他常见的iomanip标准库函数
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>&nbsp;setfill(n)</td> 
>    <td> <p>&nbsp;设置字符填充，c可以是字符常或字符变量</p> </td> 
>   </tr> 
>   <tr> 
>    <td>&nbsp;setprecision(n)</td> 
>    <td>&nbsp;设置浮点数的有效数字为n位</td> 
>   </tr> 
>   <tr> 
>    <td>&nbsp;setw(n)</td> 
>    <td>&nbsp;设置字段宽度为n位</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>     #include <iostream>
>     #include <iomanip> // 包含设置格式的库
>     
>     using namespace std;
>     
>     int main() {
>         char c = '#';
>         double num = 3.14159265359;
>     
>         cout << setfill(c) << setw(10) << "hello" << endl; // 输出 "####hello"
>         cout << fixed << setprecision(3) << num << endl; // 输出 "3.142"
>         cout << setfill('0') << setw(6) << 42 << endl; // 输出 "000042"
>     
>       return 0;
>     }
>     
>

## 二、字符串的操作 ##

### 2.1字符串的基本操作 ###

> 字符串的基本操作 string s,t;
> 
>  *  赋值：s=“pear”; t=s;
>  *  关系判断： s<t
>  *  s==t
>  *  连接： s+t 添加：
>  *  s+=t；
>  *  s.append(t);
>  *  s.push\_back(‘a’);
>  *  交换：swap（）
>  *  s.swap( t )
>  *  长度：s.length（） s.size( )

### 2.2字符串的常见操作 ###

#### 2.2.1字符串的访问 ####

> 1.  使用下标运算符\[\]。例如：
>     
>         string str = "Hello";
>         cout << str[0] << endl; // 输出 H
> 2.  使用at()函数。例如：
>     
>         string str = "Hello";
>         cout << str.at(0) << endl; // 输出 H
> 3.  substr()函数获取子串
> 
> string substr(int pos=0, int len=string::npos) const; 获取从下标pos开始的len个字符形 成子串，如果省略len或者pos+len超出字符串长度则默认到最后一个字符。
> 
>     string str = "Hello World";
>     string substr = str.substr(0, 5); // 获取 "Hello"

#### 2.2.2字符串的查找 ####

> 1.find()函数用于在string字符串中查找子字符串第一次出现的位置。
> 
>     size_t find (const string& str, size_t pos = 0) const;
> 
> 第一个参数为待查找的子字符串，它可以是string字符串，也可以是C风格的字符串。第二个参数为查找的起始位置，默认值为0。
> 
>     string str = "Hello World";
>     int index = str.find("World"); // 获取 6
> 
> 2.rfind()函数用于在字符串中从后向前查找子串（字符）首次出现位置(rfind从后向前逆向查，但匹配是正向匹配的)
> 
>     size_t rfind (const string& str, size_t pos = npos) const;
> 
> 第一个参数为待查找的子字符串，它可以是string字符串，也可以是C风格的字符串。第二个参数为查找的起始位置，默认值为npos。
> 
>     string str = "Hello World";
>     int index = str.rfind("o"); // 获取 7
> 
> 3.s.find\_first\_of(str)和s.find\_last\_of(str)
> 
> 找到目标字符在字符串中第一次出现和最后一次出现的位置
> 
>     #include<bits/stdc++.h>
>     #include<iostream>
>     using namespace std;
>     int main(){
>        string s,c;
>        s="baaaaab";
>        c="b";
>        cout<<"first index:"<<s.find_first_of(c)<<endl;
>        cout<<"last index:"<<s.find_last_of(c)<<endl;
>     }
> 
> 4查找目标字符串在字符串出现的总次数
> 
>     #include<bits/stdc++.h>
>     #include<iostream>
>     
>     using namespace std;
>     
>     int main(){
>         // 定义两个字符串变量s和c，分别存储原始字符串和子串
>         string s,c;
>         // 定义两个整数变量index和sum，分别存储当前匹配的位置和总匹配次数
>         int index,sum;
>         // 初始化index和sum为0
>         index=0;
>         sum=0;
>         // 使用while循环读入s和c，直到输入结束
>         while(cin>>s>>c){
>         // 使用while循环在s中查找c，使用find函数返回匹配的位置，如果没有匹配，返回string::npos
>             while((index=s.find(c,index))!=string::npos){
>         // 输出当前匹配的次数和位置
>             cout<<"sum: "<<sum+1<<" index: "<<index<<endl;
>          // 更新index为当前匹配位置加上c的长度，以避免重复匹配
>             index+=c.length();
>          // 更新sum为当前匹配次数加一
>             sum++;
>     }
>         // 输出最终的匹配次数
>         cout<<sum<<endl;
>     }
>         // 返回0表示程序正常结束
>         return 0;
>     }
>     /*
>     banana na
>     */
> 
> string::npos是一个常量静态成员值，它是size\_t类型的元素能表示的最大值12。它实际上表示字符串的结尾

#### 2.2.3字符串插入 ####

> 字符串insert( )函数
> 
> 在原串下标为pos的字符前插入字符串str
> 
>     basic_string& insert (size_type pos, const basic_string& str);
> 
> str从下标为pos1开始数的n个字符插在原串下标为pos的字符前
> 
>     basic_string& insert (size_type pos, const basic_string& str, size_type pos1, size_type n);
> 
> 在原串下标为pos的字符前插入n个字符c  
> 
> 
>     basic_string& insert (size_type pos, size_type n, char c);
> 
> 举例
> 
>     #include<iostream>
>     using namespace std;
>     int main()
>     {
>         string str="hello";
>         string s="Hahah";
>         str.insert(1,s);//在原串下标为1的字符e前插入字符串s
>         cout<<str<<endl;
>     
>         string str1="hello";
>         char c='w';
>         str1.insert(4,5,c);//在原串下标为4的字符o前插入5个字符c
>         cout<<str1<<endl;
>     
>         string str2="hello";
>         string s2="weakhaha";
>         str2.insert(0,s2,1,3);//将字符串s2从下标为1的e开始数3个字符，分别是eak，插入原串的下标为0的字符h前
>         cout<<str2<<endl;
>     
>         return 0;
>     }

#### 2.2.4替换字符串的子串：replace( ) 函数 ####

> 将下标pos开始的len个字符替换为特定字符串str
> 
> string& replace (size\_t pos, size\_t len, const string& str);
> 
> 将迭代器beg和end中间的字符替换为str  
> string& replace (iterator beg, iterator end, const string& str);
> 
>     #include <iostream>
>     #include <string>
>     using namespace std;
>     
>     int main() {
>       // 创建一个字符串对象
>       string s = "Hello world!";
>       // 调用第一个函数，将下标为6开始的5个字符替换为"China"
>       s.replace(6, 5, "China");
>       // 输出替换后的字符串
>       cout << s << endl; // Hello China!
>       // 调用第二个函数，将迭代器s.begin()和s.begin()+5之间的字符替换为"Hi"
>       s.replace(s.begin(), s.begin() + 5, "Hi");
>       // 输出替换后的字符串
>       cout << s << endl; // Hi China!
>       return 0;
>     }

#### 2.2.5删除字符串中的子串：erase( ）函数 ####

> 删除字符串中的子串：erase( ）函数
> 
> 删除迭代器pos指向的元素 string& erase(iterator pos);
> 
> 删除迭代器pos开始的len个字符 string& erase (iterator pos=0,size\_t len=npos);
> 
> 删除迭代器first到last中间字符 string.erase(iterator first,iterator last);
> 
>     #include <iostream>
>     #include <string>
>     using namespace std;
>     
>     int main() {
>       // 创建一个字符串对象
>       string s = "Hello world!";
>       // 调用第一个函数，删除下标为6开始的5个字符
>       s.erase(6, 5);
>       // 输出删除后的字符串
>       cout << s << endl; // Hello !
>       // 调用第二个函数，删除迭代器s.begin()+5指向的字符
>       s.erase(s.begin() + 5);
>       // 输出删除后的字符串
>       cout << s << endl; // Hello！
>       // 调用第三个函数，删除迭代器s.begin()+2和s.end()-1之间的字符
>       s.erase(s.begin() + 2, s.end() - 1);
>       // 输出删除后的字符串
>       cout << s << endl; // He!
>       return 0;
>     }

#### 2.2.6string与C风格字符串的转换 ####

![1f7b30e63ea345bf82431d53b0d413f4.png][]

> **c\_str( )函数** 
> 
> c\_str ()函数是string类的一个成员函数，它返回一个指向正规C字符串的指针常量，内容与本string串相同
> 
>     #include <iostream>
>     #include <string>
>     using namespace std;
>     
>     int main() {
>       // 创建一个字符串对象
>       string s = "Hello world!";
>       // 调用c_str ()函数，返回一个指向C字符串的指针
>       const char* c = s.c_str();
>       // 输出C字符串
>       cout << c << endl; // Hello world!
>       return 0;
>     }

### 2.3string对象的STL常用算法 ###

> string 对象也可以看作一个顺序容器，它支持随机访问迭代器，也有 begin 和 end 等成员函数。STL 中的许多算法也适用于 string 对象。 计数，查找，删除，排序等操作都可以利用STL算法来完成。

#### 2.3.1计数 ####

> count( ): 查找值value在容器中的个数，它可以用于任何支持迭代器的容器，如vector，list，set，map等。它的用法是：
> 
> count(first, last, value);
> 
> 其中first和last是容器的首尾迭代器，value是要查找的元素。它的返回值是一个整数，表示value在容器中出现的次数
> 
>     #include <iostream>
>     #include <string>
>     #include <algorithm>
>     using namespace std;
>     
>     int main() {
>       string s = "hello world"; // 定义一个string对象
>       int n = count(s.begin(), s.end(), 'l'); // 查找'l'在s中的个数
>       cout << n << endl; // 输出3
>       return 0;
>     }

#### 2.3.2排序与反序操作 ####

> sort（ ）：排序
> 
> sort(s.begin( ) , s.end( ) ）；
> 
> //对字符串中字符进行升序排序 reverse（ ）：
> 
> 反序，将序列 \[beg , end)的元素在原容器中反序
> 
> reverse（iterator beg，iterator end）；
> 
> reverse（s.begin( ) , s.end( ) ）; //对字符串进行反序
> 
>     #include <iostream>
>     #include <string>
>     #include <algorithm>
>     using namespace std;
>     
>     bool comp(char a, char b) { // 定义一个比较函数，按照字母表顺序的逆序比较字符
>       return a > b;
>     }
>     
>     int main() {
>       string s = "hello world"; // 定义一个string对象
>       sort(s.begin(), s.end()); // 对s中的字符进行升序排序
>       cout << s << endl; // 输出 dehllloorw
>       sort(s.begin(), s.end(), comp); // 对s中的字符按照comp函数指定的规则进行排序
>       cout << s << endl; // 输出 wroollldhhe
>       reverse(s.begin(), s.end()); // 将s中的字符反转
>       cout << s << endl; // 输出 ehhdllloorw
>       return 0;
>     }

#### 2.3.3删除元素remove（ ）|remove\_if（ ） ####

> remove(first, last, value); // 删除\[first, last)区间内等于value的元素，并返回新的超尾值的迭代器
> 
>      remove(iterator beg, iterator end, value);
> 
> 注意：remove函数并不是真的删除元素，它只是通过迭代器的指针向前移动来删除，将没有被删除的元素放在容器前面，并返回一个指向新的超尾值的迭代器，如果需要删除元素，需要结合对应容器的earse函数。
> 
> remove\_if（ ）函数：删除容器中满足fun函数中条件的元素，效果等同remove函数，可以用来删除多个元素。
> 
>     remove_if(iterator beg, iterator end, fun);
> 
> ![79eef8f29b9749beae7f5b6e15867d5a.png][]

#### 2.3.4替换元素 replace（）： ####

> `replace()` 是字符串的一个方法，它可以用来替换字符串中的某些字符或子串。
> 
>     replace(iterator beg, iterator end, oldvalue, newvalue);
> 
> 举例
> 
>     #include <iostream>
>     #include <string>
>     using namespace std;
>     
>     int main() {
>       string s = "Hello World"; // 定义一个string对象
>       s.replace(0, 5, "Hi"); // 用"Hi"替换从0开始长度为5的子串
>       cout << s << endl; // 输出 Hi World
>       s.replace(s.begin(), s.begin() + 3, "Bye"); // 用"Bye"替换从迭代器s.begin()到s.begin() + 3的子串
>       cout << s << endl; // 输出 Bye World
>       s.replace(4, 5, "Bye", 0 ,3); // 用"Bye"的从0开始长度为3的子串替换从4开始长度为5的子串
>       cout << s << endl; // 输出 Bye Bye
>       s.replace(0 ,3 , "Hello"); // 用C字符串"Hello"替换从0开始长度为3的子串
>       cout << s << endl; // 输出 Hello Bye
>       s.replace(s.begin(), s.begin() + 5 , "Hi"); // 用C字符串"Hi"替换从迭代器s.begin()到s.begin() + 5的子串
>       cout << s << endl; // 输出 Hi Bye
>       s.replace(0 ,2 , "Hello", 3); // 用C字符串"Hello"的前3个字符替换从0开始长度为2的子串
>       cout << s << endl; // 输出 Hel Bye
>       s.replace(s.begin(), s.begin() +3 , "Hi",2); // 用C字符串"Hi"的前2个字符替换从迭代器s.begin()到s.begin() +3 的子串
>       cout << s << endl; // 输出 Hi Bye
>       s.replace(0 ,2 ,3 ,'*'); // 用3个字符'*'替换从0开始长度为2的子串
>       cout << s << endl; // 输出 *** Bye
>       s.replace(s.begin(), s.end(), "Hello World"); // 用"Hello World"替换从迭代器s.begin()到s.end()的子串，即整个字符串
>       cout << s << endl; // 输出 Hello World
>       return 0;
>     }

## 三、例题 ##

### 3.1反转字符串 ###

> 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。
> 
> 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
> 
> 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
> 
> 示例 1：  
> 输入：\["h","e","l","l","o"\]  
> 输出：\["o","l","l","e","h"\]
> 
> 示例 2：  
> 输入：\["H","a","n","n","a","h"\]  
> 输出：\["h","a","n","n","a","H"\]

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
    
    int main() {
        vector<char> s = {'h', 'e', 'l', 'l', 'o'};
        reverseString(s);
        for (char c : s) {
            cout << c << " ";
        }
        cout << endl;
        return 0;
    }

另一种形式

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void reverseString(vector<char>& s) {
    
         for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
    
    int main() {
        vector<char> s = {'h', 'e', 'l', 'l', 'o'};
        reverseString(s);
        for (char c : s) {
            cout << c << " ";
        }
        cout << endl;
        return 0;
    }

另一种形式

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {
        vector<char> s = {'h', 'e', 'l', 'l', 'o'};
        reverse(s.begin(),s.end());
        for (char c : s) {
            cout << c << " ";
        }
        cout << endl;
        return 0;
    }

### 3.2反转字符串II ###

> 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
> 
> 如果剩余字符少于 k 个，则将剩余字符全部反转。  
> 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。  
> 
> 
> 示例 1：
> 
> 输入：s = "abcdefg", k = 2  
> 输出："bacdfeg"  
> 示例 2：
> 
> 输入：s = "abcd", k = 2  
> 输出："bacd"  
> 
> 
> 提示：
> 
> 1 <= s.length <= 104  
> s 仅由小写英文组成  
> 1 <= k <= 104

#include <iostream>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
    
    int main() {
        string s = "abcdefg";
        int k = 2;
        string res = reverseStr(s, k);
        cout << res << endl;  // 输出：bacdfeg
    
        s = "abcd";
        k = 2;
        res = reverseStr(s, k);
        cout << res << endl;  // 输出：bacd
    
        return 0;
    }

### 3.3翻转字符串里的单词 ###

> 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
> 
> 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
> 
> 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
> 
> 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
> 
> 示例 1：
> 
> 输入：s = "the sky is blue"  
> 输出："blue is sky the"  
> 示例 2：
> 
> 输入：s = " hello world "  
> 输出："world hello"  
> 解释：反转后的字符串中不能存在前导空格和尾随空格。  
> 示例 3：
> 
> 输入：s = "a good example"  
> 输出："example good a"  
> 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。  
> 
> 
> 提示：
> 
> 1 <= s.length <= 104  
> s 包含英文大小写字母、数字和空格 ' '  
> s 中 至少存在一个 单词

#include <iostream>
    #include <vector>
    #include <string>
    #include<algorithm>
    
    using namespace std;
    
    string join(vector<string>& words, string delimiter) {
        string result = "";
        int n = words.size();
        for (int i = 0; i < n; i++) {
            result += words[i];
            if (i < n - 1) {
                result += delimiter;
            }
        }
        return result;
    }
    
    string reverseWords(string s) {
        vector<string> words; // 存储单词的vector
        string word = ""; // 存储当前单词的字符串
        for (char c : s) {
            if (c == ' ') { // 遇到空格，当前单词结束，将其加入vector中
                if (!word.empty()) {
                    words.push_back(word);
                    word = "";
                }
            } else { // 不是空格，将字符加入当前单词的字符串中
                word += c;
            }
        }
        if (!word.empty()) {
            words.push_back(word); // 将最后一个单词加入vector中
        }
        reverse(words.begin(), words.end()); // 翻转vector
        string word0 = join(words, " ");
        return word0; // 使用string的join方法连接单词
    }
    
    int main() {
        string s1 = "the sky is blue";
        cout << reverseWords(s1) << endl; // "blue is sky the"
    
        string s2 = "  hello world  ";
        cout << reverseWords(s2) << endl; // "world hello"
    
        string s3 = "a good   example";
        cout << reverseWords(s3) << endl; // "example good a"
    
        return 0;
    }

#### 快慢指针 ####

#include <iostream>
    #include <string>
    #include<algorithm>
    using namespace std;
    
    // 定义一个函数，用于去除字符串中多余的空格
    void removeExtraSpaces(string& s) {
        int slow = 0; // 定义一个慢指针，用于记录去除空格后的字符串长度
        for (int i = 0; i < s.size(); ++i) { // 遍历字符串中的每个字符
            if (s[i] != ' ') { // 如果当前字符不是空格
                if (slow != 0) s[slow++] = ' '; // 如果慢指针不为零，说明前面已经有单词了，需要在单词间加一个空格
                while (i < s.size() && s[i] != ' ') { // 把当前单词的所有字符复制到慢指针指向的位置
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); // 调整字符串的大小为慢指针的值，去除末尾多余的空格
    }
    // 定义一个函数，用于反转字符串中的单词顺序
    void reverseWords(string& s) {
    
        removeExtraSpaces(s); // 先调用上面定义的函数，去除字符串中多余的空格
        reverse(s.begin(), s.end()); // 反转整个字符串，使用<algorithm>库中的reverse函数
        int start = 0; // 定义一个变量，用于记录每个单词的起始位置
        for (int i = 0; i < s.size(); ++i) { // 遍历字符串中的每个字符
            if (s[i] == ' ') { // 如果当前字符是空格，说明找到了一个单词的结束位置
                reverse(s.begin() + start, s.begin() + i); // 反转这个单词，使用<algorithm>库中的reverse函数
                start = i + 1; // 更新下一个单词的起始位置为当前位置加一
            }
        }
        reverse(s.begin() + start, s.end()); // 反转最后一个单词，使用<algorithm>库中的reverse函数
    }
    
    
    
    int main() {
        string s1 = "the                   sky is blue";
        //removeExtraSpaces(s1);
        reverseWords(s1);
        cout << s1 << endl;  // 输出 "blue is sky the"
    
        string s2 = "  hello world  ";
        reverseWords(s2);
        cout << s2 << endl;  // 输出 "world hello"
    
        string s3 = "a good   example";
        reverseWords(s3);
        cout << s3 << endl;  // 输出 "example good a"
    
        return 0;
    }

### 3.4KMP算法 ###

#### 实验书模板 ####

#include <iostream>
    #include<cstring>
    using namespace std;
    bool getNext(char T[], int length, int *next) {
        int i = 1;
        int j = 0;
        next[i-1] = 0;
        while(i < length) {
            if(j == 0 || T[i-1] == T[j-1]) {
                i ++;
                j ++;
                next[i-1] = j;
            }
            else {
                j = next[j-1];
            }
        }
        return true;
    }
    
    void getnextval(char T[], int lengtht, int *nextval) {
        int i = 1;
        int j = 0;
        nextval[i-1] = 0;
        while(i < lengtht) {
            if(T[i-1] == T[j-1] || j == 0) {
                i ++;
                j ++;
                if(T[i-1] != T[j-1]) nextval[i-1] = j;
                else nextval[i-1] = nextval[j-1];
            }
            else j = nextval[j-1];
        }
    }
    
    int KMP(char S[], int lengths, char T[], int lengtht) {
        int *next;
        next = new int[lengtht];
        getNext(T, lengtht, next);
        for(int i = 0; i < lengtht; i ++) {
            cout << *(next + i) << " ";
        }
        cout << endl;
        int *nextval;
        nextval = new int[lengtht];
        getnextval(T, lengtht, nextval);
        for(int i = 0; i < lengtht; i ++) {
            cout << *(nextval + i) << " ";
        }
        cout << endl;
        int i = 1;
        int j = 1;
        while(i <= lengths && j <= lengtht) {
            if(j == 0 || S[i-1] == T[j-1]) {
                i ++;
                j ++;
            }
            else {
                j = next[j-1];
            }
        }
        if(j > lengtht) return i - lengtht;
        else return -1;
    }
    
    int main() {
        char S[] = "abagooglegg";
        char T[] = "abcaabbcabcaabdab";
        //char S[100],T[100];
        //cin>>S;
        //cin>>T;
        int lengths = strlen(S);
        int lengtht = strlen(T);
        int res = KMP(S,lengths, T,lengtht);
        cout << res;
        cout << endl;
        return 0;
    }

具体题目

> 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
> 
> 示例 1：
> 
> 输入：haystack = "sadbutsad", needle = "sad"  
> 输出：0  
> 解释："sad" 在下标 0 和 6 处匹配。  
> 第一个匹配项的下标是 0 ，所以返回 0 。  
> 示例 2：
> 
> 输入：haystack = "leetcode", needle = "leeto"  
> 输出：-1  
> 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。  
> 
> 
> 提示：
> 
> 1 <= haystack.length, needle.length <= 104  
> haystack 和 needle 仅由小写英文字符组成

#### 暴力匹配 ####

// 暴力匹配
    int i = 0, j = 0;
    while (i < s.length())
    {
        if (s[i] == p[j])
            ++i, ++j;
        else
            i = i - j + 1, j = 0;
        if (j == p.length())  // 匹配成功
        {
            // 对s[i - j .. i - 1]进行一些操作
            cout << i - j << endl;
            i = i - j + 1;
            j = 0;
        }
    }

KMP

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    void getNext(int* next, const string& s) {
        int j = 0;      //表示前缀的末尾
        next[0] = 0;    //next[0]初始化为0
        for(int i = 1; i < s.size(); i++) {    //i表示后缀的末尾
            while (j > 0 && s[i] != s[j]) {   //当j>0且两个字符不相等时，往前跳
                j = next[j - 1];    //因为j是前缀末尾，所以需要找到前缀的前缀的末尾
            }
            if (s[i] == s[j]) { //如果相等，最长匹配数加1
                j++;
            }
            next[i] = j;    //将最长匹配数保存在next数组中
        }
    }
    
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {   //如果needle为空，返回0
            return 0;
        }
        int next[needle.size()];    //定义next数组，大小为needle的长度
        getNext(next, needle);  //求next数组
        int j = 0;  //j表示模式串needle的下标
        for (int i = 0; i < haystack.size(); i++) { //i表示主串haystack的下标
            while(j > 0 && haystack[i] != needle[j]) {    //当两个字符不相等时，往前跳
                j = next[j - 1];    //因为j是前缀末尾，所以需要找到前缀的前缀的末尾
            }
            if (haystack[i] == needle[j]) { //如果相等，最长匹配数加1
                j++;
            }
            if (j == needle.size() ) {  //如果j等于模式串needle的长度，说明完全匹配
                return (i - needle.size() + 1); //返回下标，因为i是主串下标，所以需要减去needle的长度，加1是因为数组下标从0开始
            }
        }
        return -1;  //未匹配成功，返回-1
    }
    
    int main() {
        string haystack = "hello world";
        string needle = "lo";
        int index = strStr(haystack, needle);
        cout << index << endl;  //预期输出为3
    
        haystack = "aaaaa";
        needle = "bba";
        index = strStr(haystack, needle);
        cout << index << endl;  //预期输出为-1
    
        return 0;
    }

### 3.5重复的子字符串 ###

> 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
> 
> 示例 1:  
> 输入: "abab"  
> 输出: True  
> 解释: 可由子字符串 "ab" 重复两次构成。
> 
> 示例 2:  
> 输入: "aba"  
> 输出: False
> 
> 示例 3:  
> 输入: "abcabcabcabc"  
> 输出: True  
> 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

#### 暴力解法 ####

#include <iostream>
    #include <string>
    
    using namespace std;
    
    bool repeatedSubstringPattern(string s) {
      int n = s.size();
    
      // 枚举所有可能的子串长度
      for (int len = 1; len <= n/2; len++) {
        if (n % len == 0) { // 如果字符串长度是子串长度的整数倍
          bool flag = true;
          string substr = s.substr(0, len); // 取出第一个子串
    
          // 逐个检查所有子串是否相同
          for (int i = len; i < n; i += len) {
            string temp = s.substr(i, len);
            if (temp != substr) {
              flag = false;
              break;
            }
          }
    
          if (flag) {
            return true;
          }
        }
      }
    
      return false;
    }
    
    int main() {
      string s1 = "abab";
      string s2 = "aba";
      string s3 = "abcabcabcabc";
    
      cout << repeatedSubstringPattern(s1) << endl; // 输出 "1"，即 true
      cout << repeatedSubstringPattern(s2) << endl; // 输出 "0"，即 false
      cout << repeatedSubstringPattern(s3) << endl; // 输出 "1"，即 true
    
      return 0;
    }

#### 移动匹配 ####

#include <iostream>
    #include <string>
    
    using namespace std;
    
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // 如果 t 中包含 s，返回 true
        return false;
    }
    
    int main() {
        string s = "abcabcabcabc";
        if (repeatedSubstringPattern(s)) {
            cout << "The string \"" << s << "\" can be formed by repeating a substring." << endl;
        } else {
            cout << "The string \"" << s << "\" cannot be formed by repeating a substring." << endl;
        }
        return 0;
    }

####  ####

[c78c8fe0510340feb184d92c2f3324b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/a562aed749ed4bd8a74eaac34a1f1893.png
[Link 1]: https://so.csdn.net/so/search?q=%E5%A4%B4%E6%96%87%E4%BB%B6&spm=1001.2101.3001.7020
[3c357cb77df643fdac361ca882f69e07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/7265c743154f4b128f5d99737788c361.png
[1f7b30e63ea345bf82431d53b0d413f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/58e0d294b3da49e1b20f736a05d4c512.png
[79eef8f29b9749beae7f5b6e15867d5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/7d521a77aa754d8eb96271890dd92ac3.png