C++ 算法题：强迫症的真真 - 查找最短包含3个'z'的子串

题目背景

真真患上了强迫症，比如每天早上都要吃两个包子

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

happyzazziohell

样例输出 #1

样例 #2

样例输入 #2

xoizz

样例输出 #2

zzz

C++ 代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

char s[N];
int f[N];

int main()
{
    scanf('%s', s + 1);
    int n = strlen(s + 1);

    const char* t = 'zzz';
    int len = strlen(t);

    int res = n + 1;
    for (int i = 1, j = 0, k = 0; i <= n; i ++ )
    {
        if (s[i] == 'z') j ++ ;
        if (j == 3)
        {
            while (s[k + 1] != 'z') k ++ ;
            j -- ;
            k ++ ;
        }
        f[i] = i - k + 1;
        if (i >= len && !memcmp(t, s + i - len + 1, len))
            res = min(res, f[i - len]);
    }

    if (res == n + 1) puts('zzz');
    else printf('%d\n', res);

    return 0;
}

代码解析

初始化：
- 使用 const char* t = 'zzz'; 定义目标字符串 t 。
- 使用 int len = strlen(t); 获取目标字符串的长度 len 。
- 使用 int res = n + 1; 初始化结果变量 res，将其设置为字符串长度加 1，这样在没有找到符合条件的子串时， res 仍然是一个较大的值。
遍历字符串：使用 for 循环遍历字符串 s，使用三个变量：
- i：当前遍历到的字符的下标。
- j：当前子串中 'z' 的数量。
- k：当前子串中最左边的 'z' 的下标。
维护子串信息：
- 如果当前字符 s[i] 是 'z'，则 j 加 1。
- 如果 j 等于 3，表示当前子串包含 3 个 'z'，则需要更新 k，找到当前子串中最左边的 'z'。
更新结果：
- 使用 f[i] = i - k + 1; 计算当前子串的长度。
- 如果当前子串的长度大于等于目标字符串的长度 len，并且当前子串与目标字符串 t 相同，则更新 res 为当前子串的长度。
输出结果：
- 如果 res 仍然是初始值 n + 1，表示没有找到符合条件的子串，输出 'zzz' 。
- 否则输出 res。

总结

本算法题使用了滑动窗口和字符串比较的方法，高效地找到了给定字符串中包含 3 个 'z' 的最短子串，体现了算法设计中的灵活性和优化技巧。

希望本解析能够帮助您理解代码，并学会运用类似的方法解决类似的算法问题！

C++ 算法题：强迫症的真真 - 查找最短包含3个z的子串