C++ 编程挑战：寻找最短真真串

题目描述

真真发现他对字符串也有强迫症，他喜欢的字符串必须恰好包含 3 个 'z'。例如'poazdxzz'、'oixzzz' 都是真真喜欢的字符串，我们称为真真串。但是像'yuzz'、'deoa' 这样的字符串，真真是非常讨厌的。现在给定一个只包含小写字母的字符串 ch，请你帮助真真计算 ch 的所有子串中，最短的真真串是哪一个。对于子串，我们规定：'xoi'、'itydre' 都是 'xoitydre' 的子串，但是 'xit' 不是 'xoitydre' 的子串。

输入格式

输入一个只包含小写字母的字符串，字符串的长度不超过 100000。

输出格式

若输入的字符串的所有子串中有真真串，找到最短的真真串，输出其长度。若没有真真串，则输出'zzz' (不包含引号)。

样例

样例输入 #1

happyzazziohell

样例输出 #1

样例输入 #2

xoizz

样例输出 #2

zzz

C++ 代码实现

#include <iostream>
#include <cstring>
using namespace std;
string str;
int main() {
    cin >> str;
    int len = str.size();
    int res = len + 1;
    int l = 0, r = 0;
    int cnt = 0;
    while (r < len) {
        if (str[r] == 'z') cnt++;
        while (cnt == 3) {
            res = min(res, r - l + 1);
            if (str[l] == 'z') cnt--;
            l++;
        }
        r++;
    }
    if (res == len + 1) cout << 'zzz' << endl;
    else cout << res << endl;
    return 0;
}

解题思路

使用两个指针 l 和 r 来遍历字符串，l 指向子串的起始位置，r 指向子串的结束位置。
使用一个计数器 cnt 来统计当前子串中 'z' 的数量。
当 cnt 等于 3 时，更新最短真真串的长度 res，并将 l 向右移动，直到 cnt 不再等于 3。
如果遍历完整个字符串后，res 仍然等于 len + 1，说明没有找到真真串，输出 'zzz'；否则，输出 res。

代码解读

res = len + 1：初始化 res 为字符串长度加 1，这样如果找不到真真串，res 就不会被更新。
while (cnt == 3)：当子串中 'z' 的数量为 3 时，更新 res，并将 l 向右移动，直到 cnt 不再等于 3。
if (str[l] == 'z') cnt--;：如果 l 指向的字符为 'z'，则将 cnt 减 1。
if (res == len + 1) cout << 'zzz' << endl;：如果 res 没有被更新，说明没有找到真真串，输出 'zzz'。

总结

这道题考察的是字符串匹配问题，使用双指针和计数器的方法可以有效地解决问题。在实际应用中，可以使用类似的方法来处理各种字符串匹配问题。