AcWing语法基础课学习笔记第五讲字符串

心已赠人 2024-03-17 11:30 81阅读 0赞

### AcWing语法基础课学习笔记 ###

#### 文章目录 ####

*   *  AcWing语法基础课学习笔记
     *   *   *  第五讲 字符串
             *   *  1. 字符与整数的联系——ASCII码
                 *  2. 字符数组
                 *   *  2.1 字符数组的输入输出
                     *  2.2 字符数组的常用操作
                     *  2.3 遍历字符数组中的字符：
                 *  3. 标准库类型\`string\`
                 *   *  3.1 定义和初始化
                     *  3.2 string上的操作
                     *  3.3 处理string对象中的字符

![在这里插入图片描述][668222d12f7746b5b63c1a8e80ad06e7.png_pic_center]

##### 第五讲 字符串 #####

字符串是计算机与人类沟通的重要手段。——闫学灿

###### 1. 字符与整数的联系——ASCII码 ######

每个常用字符都对应一个`-128 ~ 127`的数字，二者之间可以相互转化。注意：目前负数没有与之对应的字符。

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        char c = 'a';
        cout << (int)c << endl;
    
        int a = 66;
        cout << (char)a << endl;
    
        return 0;
    }

![在这里插入图片描述][beba9a3ca97c42e392473b24178de199.png_pic_center]

常用ASCII值：`'A'- 'Z'`是`65 ~ 90`，`'a' - 'z'`是`97 - 122`，`0 - 9`是 `48 - 57`。

字符可以参与运算，运算时会将其当做整数：

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int a = 'B' - 'A';
        int b = 'A' * 'B';
        char c = 'A' + 2;
    
        cout << a << endl;
        cout << b << endl;
        cout << c << endl;
    
        return 0;
    }

![在这里插入图片描述][824e17cbbe5d4d6986045a55cc6ffcd6.png_pic_center]

###### 2. 字符数组 ######

字符串就是字符数组加上结束符`'\0'`。【`√`】

可以使用字符串来初始化字符数组，但此时要注意，每个字符串结尾会暗含一个`'\0'`字符，因此字符数组的长度至少要比字符串的长度多 `1` ！

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        char a1[] = {'C', '+', '+'};            // 列表初始化，没有空字符
        char a2[] = {'C', '+', '+', '\0'};      // 列表初始化，含有显示的空字符
        char a3[] = "C++";                      // 自动添加表示字符串结尾的空字符
        char a4[6] = "Daniel";                  // 错误：没有空间可以存放空字符
    
        return 0;
    }

![在这里插入图片描述][f45ab78a27c04786b95257ac76509e6d.png_pic_center]

###### 2.1 字符数组的输入输出 ######

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        char str[100];
    
        cin >> str;             // 输入字符串时，遇到空格或者回车就会停止
        cout << str << endl;    // 输出字符串时，遇到空格或者回车不会停止，遇到'\0'时停止
        printf("%s\n", str);
    
        return 0;
    }

![在这里插入图片描述][a01b3a6cb3de4eb59d7638e9a487e7bb.png_pic_center]

> 用`scanf` 读入字符数组时，别加 `&`

读入一行字符串，包括空格：

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        char str[100];
    
        fgets(str, 100, stdin);  // gets函数在新版C++中被移除了，因为不安全。
                                 // 可以用fgets代替，但注意fgets不会删除行末的回车字符
    
        cout << str << endl;
    
        return 0;
    }

![在这里插入图片描述][8162fc972150486dbddcbefe787b72c2.png_pic_center]

> `fgets()` 新函数

###### 2.2 字符数组的常用操作 ######

> 【字符数组】的常用操作

下面几个函数需要引入头文件: `#include<string.h>`

*  (1) `strlen(str)`，求字符串的长度
 *  (2) `strcmp(a, b)`，比较两个字符串的大小，a < b返回`-1`，a == b返回`0`，a > b返回`1`。这里的比较方式是字典序！
 *  (3) `strcpy(a, b)`，将字符串b复制给从a开始的字符数组。

#include <iostream>
    #include <string.h>
    
    using namespace std;
    
    int main()
    {
        char a[100] = "hello world!", b[100];
    
        cout << strlen(a) << endl;
    
        strcpy(b, a);
    
        cout << strcmp(a, b) << endl;
    
        return 0;
    }

![在这里插入图片描述][a055b1972103474c972549d9b37c61b8.png_pic_center]

###### 2.3 遍历字符数组中的字符： ######

#include <iostream>
    #include <string.h>
    
    using namespace std;
    
    int main()
    {
        char a[100] = "hello world!";
    
        // 注意：下述for循环每次均会执行strlen(a)，运行效率较低，最好将strlen(a)用一个变量存下来
        for (int i = 0; i < strlen(a); i ++ )
            cout << a[i] << endl;
    
        return 0;
    }

![在这里插入图片描述][01d118c4132b49118d1a4bf7e9475f9e.png_pic_center]

练习：给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出no。

`AcWing 772. 只出现一次的字符`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    char str[100010];
    int cnt[26];
    
    int main(){
        
        cin >> str;
        
        int len = strlen(str);
        for(int i = 0; i < len; i ++) cnt[str[i] - 'a'] ++;
        
        for(int i = 0; i < strlen(str); i++)
            if(cnt[str[i] - 'a'] == 1)
            {
                cout << str[i] << endl;
                return 0;
            }
        
        puts("no");
        
        return 0;
    }

> 反正算长度拿出来单独算一次就行了， 别在循环里面算
> 
> 循环条件还可以直接写成`str[i]`，因为字符数组最后是有一个`\0`
> 
> ![在这里插入图片描述][f059de5c7a984339a2c622a5e2992335.png_pic_center]
> 
> 这样也可以过掉
> 
> ![在这里插入图片描述][5b0d5c1498ac4d8cabc953ff26445d0a.png_pic_center]
> 
> 时间也更快
> 
> ![在这里插入图片描述][eee9938aa4fd4ee6afea2e44c67efb33.png_pic_center]
> 
> 好吧其实看不出来区别

练习：把一个字符串中特定的字符全部用给定的字符替换，得到一个新的字符串。

`AcWing 769. 替换字符`

#include <cstring>
    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    char str[35];
    
    int main(){
        
        char t;
        
        cin >> str >> t;
        
        for(int i = 0; str[i] ; i ++)
            
            if(str[i] == t) str[i] = '#';
            
        puts(str);
        
        return 0;
    }

###### 3. 标准库类型`string` ######

可变长的字符序列，比字符数组更加好用【80% 的情况我们都不会自己去搞一个字符数组的】。需要引入头文件：

#include <string>
    
    // 或者写
    
    #include <cstring>

###### 3.1 定义和初始化 ######

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s1;              // 默认初始化，s1是一个空字符串
        string s2 = s1;         // s2是s1的副本，注意s2只是与s1的值相同，并不指向同一段地址
        string s3 = "hiya";     // s3是该字符串字面值的副本
        string s4(10, 'c');     // s4的内容是 "cccccccccc"
    
        return 0;
    }

![在这里插入图片描述][3db46de39c5844e197df26ed97ea910a.png_pic_center]

###### 3.2 string上的操作 ######

(1) `string`的读写：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s1, s2;
    
        cin >> s1 >> s2;
        cout << s1 << s2 << endl;
    
        return 0;
    }

![在这里插入图片描述][8113652ec3ea4d4fb8438dbfda3deac2.png_pic_center]

![在这里插入图片描述][53d791c39bee452881ed728c3bcf05cd.png_pic_center]

> 注意：不能用`printf`直接输出`string`，需要写成：`printf("%s", s.c_str());`
> 
> ![在这里插入图片描述][f3dca3f73e204c56980dc6432c5ebc6c.png_pic_center]
> 
> 错误的写法：
> 
> ![在这里插入图片描述][52da871d7a004016b567b09e03bb2f0e.png_pic_center]
> 
> > 【注意】没法儿用`scanf` 直接读入`string` 变量
> 
> 当然输出还可以用`puts(s);` ，这个函数会自带一个换行

(2) 使用`getline`读取一整行

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s;
    
        getline(cin, s);
    
        cout << s << endl;
    
        return 0;
    }

![在这里插入图片描述][f811363e0c0944b4ba930b61e27070a8.png_pic_center]

(3) `string`的`empty`和`size`操作（注意`size`是**无符号整数**，因此 `s.size() <= -1`一定成立）：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s1, s2 = "abc";
    
        cout << s1.empty() << endl;
        cout << s2.empty() << endl;
    
        cout << s2.size() << endl;
    
        return 0;
    }

![在这里插入图片描述][8fe43999320c4629a8019b402aadd034.png_pic_center]

![在这里插入图片描述][709c2149697d4f6bb8b759950d432848.png_pic_center]

> 而且注意这个`size()` 函数，复杂度是`o(1)` 的，就是专门有那么个变量来存了这个长度，而`strlen()` 是每次都计算字符数组的长度，非常耗时。
> 
> 还有个`length()` ，和`size()` 完全等价

(4) `string`的比较：

支持 `>`, `<`, `>=`, `<=`, `==`, `!=`等所有比较操作，按字典序进行比较。

(5) 为`string`对象赋值：

string s1(10, 'c'), s2;     // s1的内容是 cccccccccc；s2是一个空字符串
    s1 = s2;                    // 赋值：用s2的副本替换s1的副本, 此时s1和s2都是空字符串

![在这里插入图片描述][96cbae0cf92c41a3bba1d1130b63c5ea.png_pic_center]

![在这里插入图片描述][e10ad53ef7e249c2a24248363cc968a2.png_pic_center]

(6) 两个`string`对象相加：

string s1 = "hello,  ", s2 = "world\n";
    string s3 = s1 + s2;                    // s3的内容是 hello, world\n
    s1 += s2;                               // s1 = s1 + s2

![在这里插入图片描述][b89f5641864946ceb2dab2ea81c59675.png_pic_center]

(7) 字面值和`string`对象相加：

做加法运算时，字面值和字符都会被转化成`string`对象，因此直接相加就是将这些字面值串联起来：

string s1 = "hello", s2 = "world";      // 在s1和s2中都没有标点符号
    string s3 = s1 + ", " + s2 + '\n';

![在这里插入图片描述][2481586ef4cb462186ac14c1e6b3046a.png_pic_center]

当把`string`对象和字符字面值及字符串字面值混在一条语句中使用时，必须确保每个加法运算符的两侧的运算对象至少有一个是`string`：

string s4 = s1 + ", ";  // 正确：把一个string对象和一个字面值相加
    string s5 = "hello" + ", "; // 错误：两个运算对象都不是string
    
    string s6 = s1 + ", " + "world";  // 正确，每个加法运算都有一个运算符是string
    string s7 = "hello" + ", " + s2;  // 错误：不能把字面值直接相加，运算是从左到右进行的

![在这里插入图片描述][49a4350175534ef790d329e72edcc38a.png_pic_center]

![在这里插入图片描述][6233aff0d8624c5ca1145c2879dc417e.png_pic_center]

![在这里插入图片描述][d1a66b5f155d4b4d8fec702b1f7942c7.png_pic_center]

![在这里插入图片描述][5ad07fdc46884d46a6cb8eef2211b570.png_pic_center]

> 两个"" 这样的字面量不能直接相加，会报错。

###### 3.3 处理string对象中的字符 ######

可以将`string`对象当成字符数组来处理：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s = "hello world";
    
        for (int i = 0; i < s.size(); i ++ )
            cout << s[i] << endl;
    
        return 0;
    }

![在这里插入图片描述][cceb285db3bf4b579e2a5c6e050071a6.png_pic_center]

或者使用基于范围的`for`语句：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int main()
    {
        string s = "hello world";
    
        for (char c: s) cout << c << endl;
    
        for (char& c: s) c = 'a';
    
        cout << s << endl;
    
        return 0;
    }

![在这里插入图片描述][3a61e5638d4f43e9a4572eb5e56404cc.png_pic_center]

> 注意：这里有个新知识点， `auto`，c++ 可以猜它的变量类型，当然它有可能会猜错，猜对就OK，猜错就报错【自动类型推导】

练习：密码翻译，输入一个只包含小写字母的字符串，将其中的每个字母替换成它的后继字母，如果原字母是`'z'`，则替换成`'a'`。

`AcWing 767. 信息加密`

#include <cstring>
    #include <iostream>
    
    using namespace std;
    
    int main(){
        
        string s;
        
        getline(cin , s);
        
        for(auto &c : s)
            if(c >= 'a' && c <= 'z') c = (c - 'a' + 1) % 26 + 'a';
            else if(c >= 'A' && c <= 'Z') c = (c - 'A' + 1) % 26 + 'A';
        
        cout << s << endl;
        
        return 0;
    }

> 公式：将英文字母转换为下一个，z 变为 a，Z 变为 A，`(c - 'a' + 1) % 26 + 'a'`
> 
> 这道题因为有空格，所以直接用`getline` 方便读入

OK， 开始习题：

`AcWing 760. 字符串长度`

#include <cstring>
    #include <iostream>
    
    using namespace std;
    
    int main(){
        
        string s;
        getline(cin , s);
        
        cout << s.size() << endl;
        
        return 0;
    }

> 方法很多

`AcWing 761. 字符串中的数字个数`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        int cnt = 0;
        
        string s;
        getline(cin , s);
        
        for(auto &c : s)
            if(c <= 57 && c >= 48)
                cnt ++;
        
        cout << cnt << endl;
        
        return 0;
    }

> 数字0-9的ASCII码值为 48 → 57
> 
> ![在这里插入图片描述][f8af8cdcef5a43a79dfe29bd5b966645.png_pic_center]

`AcWing 763. 循环相克令`

#include <cstring>
    #include <iostream>
    
    using namespace std;
    
    int main(){
        
        int t;
        cin >> t;
        
        while(t -- ){
            
            string s1, s2;
            cin >> s1 >> s2;
            
            int x, y;
            if(s1 == "Hunter") x = 0;
            else if(s1 == "Bear") x = 1;
            else x = 2;
            
            if(s2 == "Hunter") y = 0;
            else if(s2 == "Bear") y = 1;
            else y = 2;
            
            if(x == y) cout << "Tie" << endl;
            else if(x == (y + 1) % 3) cout << "Player1" << endl;
            else cout << "Player2" << endl;
        }
        
        return 0;
    }

> 我们可以用数字简化字符串
> 
> ![在这里插入图片描述][a8c02588eb8b4372b8d5659e5c4fae7c.png_pic_center]

`AcWing 765. 字符串加空格`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        string s;
        getline(cin , s);
        
        string res;
        
        for(auto &c : s) res = res + c + ' ';
        
        cout << res << endl;
        
        return 0;
    }

> 这道题的注意点是`c + ' '` ，不能用`+=`，两个字符不能直接相加，前面把`res` 带上，
> 
> 当然强迫症可以使用`res.pop_back()` 把最后一个空格删掉，不删不影响结果

`AcWing 773. 字符串插入`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        string a, b;
        
        while(cin >> a >> b){
            
            int p = 0;
            
            for(int i = 1; i < a.size() ; i ++){
                if(a[i] > a[p]) p = i;
            }
            
            cout << a.substr(0, p + 1) + b + a.substr(p + 1) << endl;
        }
        
        
        return 0;
    }

> 新函数`substr()`，
> 
>  *  两个参数时：开始位置，长度【相当于半闭】
>  *  一个参数时，开始位置【到结尾】
> 
> ![在这里插入图片描述][dcbbe6cee1644292b336ea7d440eac5a.png_pic_center]

`AcWing 762. 字符串匹配`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        double k;
        string a, b;
        
        int cnt = 0;
        
        cin >> k >> a >> b;
        
        for(int i = 0 ; i < a.size(); i ++)
            if(a[i] == b[i])
                cnt ++;
        
        if((double)cnt / a.size() >= k) cout << "yes" << endl;
        else cout << "no" << endl;
        
        return 0;
    }

`AcWing 768. 忽略大小写比较字符串大小`

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int main(){
        
        string a, b;
        
        getline(cin , a);
        getline(cin , b);
        
        for(int i = 0; i < a.size(); i ++)
            if(a[i] >= 'A' && a[i] <= 'Z')
                a[i] += 32;
        
        for(int i = 0; i < b.size(); i ++)
            if(b[i] >= 'A' && b[i] <= 'Z')
                b[i] += 32;
                
        if(a == b) cout << '=' << endl;
        else if(a < b) cout << '<' << endl;
        else cout << '>' << endl;
        
        return 0;
    }

> y 总这里用的是字符数组，使用`strcmp` 进行比较

`AcWing 766. 去掉多余的空格`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        string s;
        
        while(cin >> s) cout << s << ' ';
        
        return 0;
    }

> 这道题取巧的地方，就是利用读的时候自动把多余空格过滤掉即可
> 
> 当然也可以硬做
> 
> ![在这里插入图片描述][3828fc2da84448e988eb90192f14bd34.png_pic_center]
> 
> 这样也能AC，重点就是利用变量来跳过多余的空格(双指针`i`和`j`的味道)
> 
>     int j = i;
>     while(j < s.size() && s[j] == ' ') j ++;
>     i = j - 1;
> 
> 还可以直接做判断【局部性判断】
> 
> ![在这里插入图片描述][e253ee3814ef47d58727d52e11a426b2.png_pic_center]
> 
> 这样也能AC，这样的话就是判断前后字符的一个关系了

`AcWing 764. 输出字符串`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        string a, b;
        
        getline(cin , a);
        
        for(int i = 0; i < a.size(); i ++) b += a[i] + a[(i + 1) % a.size()];
        
        cout << b << endl;
        
        return 0;
    }

> 小技巧，取模来处理最后那一次

`AcWing 770. 单词替换`

#include <iostream>
    #include <cstring>
    #include <sstream>
    
    using namespace std;
    
    int main(){
        
        string s, a, b;
        
        getline(cin , s);
        
        cin >> a >> b;
        
        stringstream ssin(s);
        string str;
        
        while(ssin >> str)
            if(str == a) cout << b << ' ';
            else cout << str << ' ';
        
        return 0;
    }

> 这里有个字符串流的新知识
> 
> `stringstream` 可以将一个字符串初始化成一个类似于`cin` 的东西，然后就可以从这个东西中提取出我们需要的信息，
> 
> 比如这样
> 
> ![在这里插入图片描述][556c10935cf44f68a980211f6e365dde.png_pic_center]
> 
> 当然这个顺序和我们的`>>` 顺序有关系，`ssin` 只是一个变量名，而且它忽略中间的多余空格【这是`string`】
> 
> 字符数组也有类似的用法`sscanf()`
> 
> ![在这里插入图片描述][0f72f8a02b754b7b8e8ac7bffa5745b6.png_pic_center]
> 
> 这样也可以【当然常用的还是`stringstream`，特别是不知道一行有多少个数据的时候】

`AcWing 771. 字符串中最长的连续出现的字符`

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int main(){
        
        int n;
        cin >> n;
        
        while(n --){
            
            string s;
            cin >> s;
            
            int cnt = 0;
            char c;
            
            for(int i = 0;i < s.size(); i ++){
                
                int j = i;
                while(j < s.size() && s[j] == s[i]) j ++;
                
                if(j - i > cnt){
                    cnt = j - i;
                    c = s[i];
                }
                i = j - 1;
            }
            
            
            cout << c << ' ' << cnt << endl;
        }
        
        return 0;
    }

> 第一类双指针算法：
> 
> ![在这里插入图片描述][4207ad0849574bdbab83f4b1774dec58.png_pic_center]

`AcWing 774. 最长单词`

#include <iostream>
    
    using namespace std;
    
    int main(){
        
        string res, str;
        
        while(cin >> str){
            
            if(str.back() == '.') str.pop_back();
            
            if(str.size() > res.size()) res = str;
        }
        
        cout << res << endl;
        
        return 0;
    }

> `str.back()` 返回字符串最后一个字符
> 
> `str.pop_back()` 去掉字符串最后一个字符

`AcWing 775. 倒排单词`

#include <iostream>
    
    using namespace std;
    
    int main(){
        
        string str[100]; //字符串数组
        
        int n = 0;
        while(cin >> str[n]) n ++;
        
        for(int i = n - 1; i >= 0; i --) cout << str[i] << ' ';
        
        
        return 0;
    }

> 字符串数组

`AcWing 776. 字符串移位包含问题`

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main(){
        
        string a, b;
        
        cin >> a >> b;
        
        if(a.size() < b.size()) swap(a, b);
        
        for(int i = 0; i < a.size() ; i ++){
            
            a = a.substr(1) + a[0]; // 移动
            
            // 判断子窜
            for(int j = 0; j + b.size() <= a.size(); j ++){
                
                int k = 0;
                for(; k < b.size(); k ++)
                    if(a[j + k] != b[k]) break;
                
                if(k == b.size()){ // 较短字符串能够匹配到最后，说明是子串
                    cout << "true" << endl;
                    return 0;
                }
            }
        }
        
        cout << "false" << endl;
        
        return 0;
    }

> 压轴题
> 
> 枚举判断子串【不用自带的函数，自己写理解】

`AcWing 777. 字符串乘方`

#include <iostream>
    
    using namespace std;
    
    int main(){
        
        string str;
        
        while(cin >> str, str != "."){
            
            int len = str.size();    
            
            for(int n = len; n ; n --) // n是重复子串的次数
                if(len % n == 0)
                {
                    int m = len / n; // m 是子串长度
                    string s = str.substr(0, m); // 第一段子串
                    
                    // 拼接
                    string r;
                    for(int i = 0; i < n; i ++) r += s;
                    
                    if(r == str) {
                        cout << n << endl;
                        break; // 从大到小，就不用额外记录最大值了，第一次遇到的就是最多次数的
                    }
                }
            
        }
        
        return 0;
    }

> 枚举，这道题最大的乘方数也就是字符串长度，即子串只有一个字符，倒回来枚举，并拼接乘方数， 碰到(匹配上)了就break，得到的一定是最大乘方数

`AcWing 778. 字符串最大跨距`

#include <iostream>
    
    using namespace std;
    
    int main(){
        
        string s, s1, s2;
        
        char c;
        while(cin >> c, c!= ',') s += c;
        while(cin >> c, c!= ',') s1 += c;
        while(cin >> c) s2 += c;
        
        // 特判
        if(s.size() < s1.size() || s.size() < s2.size()) cout << "-1" << endl;
        else{
            // 找出最左边s1 的位置
            int l = 0;
            while(l + s1.size() <= s.size()){
                
                int k = 0;
                while(k < s1.size()){
                    
                    if(s[l + k] != s1[k]) break;
                    k ++;
                }
                
                if(k == s1.size()) break;
                l ++;
            }
            
            // 找出最右边s2 的位置
            int r = s.size() - s2.size(); // 开始位置是s2长度开始的s 的位置
            while(r >= 0){
                
                int k = 0;
                while(k < s2.size()){
                    if(s[r + k] != s2[k]) break;
                    k ++;
                }
                
                if(k == s2.size()) break;
                r --;
            }
            
            //【注意】l 和 r 是s1 和 s2 字符串的起点
            l += s1.size() - 1;
            
            // 已经交叉了
            if(l >= r) cout << "-1" << endl;
            else cout << (r - l - 1) << endl;
        }
        
        return 0;
    }

> 这道题也是字符串匹配， 其实是一件事情做了两次，找到要计算的开始和结束位置，即s1 的结尾和s2 的开头【行吧，这还是简单的题，tql… 】
> 
> 如果一直左边和右边都没有匹配上，l 和 r 会分别走到右边尽头和左边尽头，这样l 一定会大于 r，没问题

`AcWing 779. 最长公共字符串后缀`

#include <iostream>
    
    using namespace std;
    
    const int N = 200;
    
    int n;
    string str[N]; // 数组长度一定是个常量【不然可能有编译器不支持】
    
    int main(){
        
        while(cin >> n, n){
            
            int len = 1000;
            
            // 求出每组数据中最小的数组长度
            for(int i = 0; i < n; i ++){ // 读入n 个字符串
                
                cin >> str[i];
                if(len > str[i].size()) len = str[i].size();
            }
            
            while(len){
                
                bool success = true; // 当前长度是否成功
                for(int i = 1; i < n ; i ++){ // 判断每个字符串与第一个(0) 字符串的匹配情况
                    
                    bool is_same = true;
                    for(int j = 0; j <= len; j ++)
                        if(str[0][str[0].size() - j] != str[i][str[i].size() - j]){
                            
                            is_same = false;
                            break;
                        }                        
                    if(!is_same) {
                        success = false;
                        break;
                    }
                }
                
                if(success) break;
                
                len --;
                
            }
            
            // 输出最长后缀
            cout << str[0].substr(str[0].size() - len) << endl;
        }
    
        return 0;
    }

> 枚举，从大到小枚举后缀长度，更多次的字符串匹配【用循环代码量增强能力】
> 
> 太强了tql

![在这里插入图片描述][85ffc91d72244e0daf40380bab905677.png_pic_center]

[668222d12f7746b5b63c1a8e80ad06e7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/cfa9fccfbe32444f98da00bfb0ec8221.png
[beba9a3ca97c42e392473b24178de199.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/4d35f9eee4cf45c6b46c6f11fffa8569.png
[824e17cbbe5d4d6986045a55cc6ffcd6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/cc51577574fb46748743278da3b47d55.png
[f45ab78a27c04786b95257ac76509e6d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/a016191a4a3a453f87149b7fb0e53452.png
[a01b3a6cb3de4eb59d7638e9a487e7bb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/a17c4563f2a849089aa64fff07f1777a.png
[8162fc972150486dbddcbefe787b72c2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/795aad57c7b548d7ada2ee279174d905.png
[a055b1972103474c972549d9b37c61b8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/3fcc8d5763fe456290444b55f5b3b33e.png
[01d118c4132b49118d1a4bf7e9475f9e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/74b4ffae49644f1ab96de773f352bc3e.png
[f059de5c7a984339a2c622a5e2992335.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/0c4d063383c743f3a810b43eeefa7fd3.png
[5b0d5c1498ac4d8cabc953ff26445d0a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/87c121c40f6c40dd802e52a27a8b5af4.png
[eee9938aa4fd4ee6afea2e44c67efb33.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/b7c266c0adfc405da90a34c773756b6e.png
[3db46de39c5844e197df26ed97ea910a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/dd750ec7a7ed45f2a8474ade38bfc263.png
[8113652ec3ea4d4fb8438dbfda3deac2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/9fbaf35fbb8942e7aaca7e0823cd75d2.png
[53d791c39bee452881ed728c3bcf05cd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/014f37cc8eab44a98a42722ec34fd935.png
[f3dca3f73e204c56980dc6432c5ebc6c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/e5710ee9c6794d499ae56de68402b693.png
[52da871d7a004016b567b09e03bb2f0e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/54629aa9f3dd48c7b8dfe3a3ace6ebed.png
[f811363e0c0944b4ba930b61e27070a8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/4193a80395e6417f9e62cdff761c4d63.png
[8fe43999320c4629a8019b402aadd034.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/11de5333d6474b619ae46afd3ba35635.png
[709c2149697d4f6bb8b759950d432848.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/32cc839594d34f60bcb751e8d824cd9d.png
[96cbae0cf92c41a3bba1d1130b63c5ea.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/fadd33c9b9bc491483e5f215fb3591d5.png
[e10ad53ef7e249c2a24248363cc968a2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/228e49849d3340908b342d9bd04b0bd8.png
[b89f5641864946ceb2dab2ea81c59675.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/5e0ccd6db14a4814bd7df373856c1910.png
[2481586ef4cb462186ac14c1e6b3046a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/20589e3aaa4a4a4db823dc3f0c1c6fc5.png
[49a4350175534ef790d329e72edcc38a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/d1765da498464389a111b652f84d47d1.png
[6233aff0d8624c5ca1145c2879dc417e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/8ff996a7ec524fd3af90886ec3c2af14.png
[d1a66b5f155d4b4d8fec702b1f7942c7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/710ed5ca69bb497dbd6efaeb09f71040.png
[5ad07fdc46884d46a6cb8eef2211b570.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/59047f1f4dd44c3bb125244fcdef7b8f.png
[cceb285db3bf4b579e2a5c6e050071a6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/44eb9de04d964b3db5f8827afcc44cef.png
[3a61e5638d4f43e9a4572eb5e56404cc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/7c2c34f757154153a6da6644f55c6289.png
[f8af8cdcef5a43a79dfe29bd5b966645.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/a70725ef73264b119b6896b7d0232de1.png
[a8c02588eb8b4372b8d5659e5c4fae7c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/5f176ae8bc8043bb983db83fdbaf37e2.png
[dcbbe6cee1644292b336ea7d440eac5a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/16bb5d3fa9ad4b88a20773d1fd54231c.png
[3828fc2da84448e988eb90192f14bd34.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/56ec8a40720c4b7b88b9df5756a53409.png
[e253ee3814ef47d58727d52e11a426b2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/a5471bb8f34e402494ca6d9960beb2ae.png
[556c10935cf44f68a980211f6e365dde.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/702bd935b301421e9270259d20fca976.png
[0f72f8a02b754b7b8e8ac7bffa5745b6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/eb2c484f624c44388bc246b211b57897.png
[4207ad0849574bdbab83f4b1774dec58.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/7a35322f468b4615a0268b64ed7c97c6.png
[85ffc91d72244e0daf40380bab905677.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/bd622323d2cf4db1b53aea4176ae73c0.png