企业官网建设流程全解析

小红的偶子串

时间限制：1 秒
空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红定义偶串为：由很多长度为2 22的、两字符相同的字符串拼接而成的字符串。例如：“aabb”，“jjjkk” 是偶串，而 “aaa”，“puup” 则不是偶串。

小红拿到了一个仅由小写字母组成的字符串，她想取一段最长的连续子串为偶串。你能帮小红求出它的长度吗？

输入描述

一个仅由小写字母组成的字符串，长度不超过200000 200000200000。

输出描述

最长的偶子串长度。

示例 1

输入：

aebbbccdaa

输出：

4

说明：“bbcc” 为最长的偶串。

数据范围与提示

• 输入字符串长度不超过200000 200000200000
• 字符串仅由小写字母组成

解题思路

本题是连续偶串最长长度的简单模拟问题。偶串定义为由若干个长度为2 22且两字符相同的块连续拼接而成。也就是说，一个偶串必须满足：长度是偶数，并且从起始位置开始，每两个相邻字符都相同。

1. 问题等价转化

• 偶串可以看作是由若干个“双字符块”组成的，每个块内两个字符相同。例如"aabb"由"aa"和"bb"两个块组成。
• 一个子串是偶串，当且仅当：
  • 子串长度为偶数；
  • 从子串起始位置开始，每隔一个字符，两个字符都相等。
• 因此，偶串的起始位置i ii必须满足s [ i ] = = s [ i + 1 ] s[i] == s[i+1]s[i]==s[i+1]，然后下一个块从i + 2 i+2i+2开始，要求s [ i + 2 ] = = s [ i + 3 ] s[i+2] == s[i+3]s[i+2]==s[i+3]，依此类推，直到遇到不满足的对或字符串结束。

2. 算法实现

由于偶串的起始位置可以是任意下标，我们分别从下标0 00和下标1 11开始，以步长2 22扫描整个字符串，这样可以覆盖所有可能的起始位置（因为任何偶串的起始下标要么是偶数，要么是奇数）。

• 维护两个指针：i表示当前连续偶串的起始位置，j表示当前检查的块的位置（每次增加2 22）。
• 遍历字符串，对于每个j：
  • 如果j到达字符串末尾（j == n-1）或者s[j] != s[j+1]，说明当前块不合法。此时，从i到j之前的子串是一个合法的偶串，长度为j - i。用该长度更新答案，然后将起始位置i重置为j + 2，继续检查后续块。
• 循环结束后，再更新一次答案（处理最后一个连续合法段）。
• 对从下标0 00和下标1 11开始的两次扫描分别执行上述过程，最终答案取两次扫描的最大值。

3. 复杂度分析

• 时间复杂度：每个字符最多被访问两次（分别从0 00和1 11开始），因此总时间复杂度为O ( n ) O(n)O(n)。字符串长度不超过200000 200000200000，非常高效。
• 空间复杂度：仅使用常数个变量，空间复杂度O ( 1 ) O(1)O(1)。

总结

通过分别从偶数下标和奇数下标开始，以步长2 22扫描字符串，并实时维护当前连续合法块的起始位置，可以在线性时间内找到最长的偶串。该方法巧妙覆盖了所有可能的起始位置，且实现简单，完全满足题目要求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string t;cin>>t;ll n=t.size();ll i=0,j=0;ll a=0;for(;j<n;j+=2){if(j==n-1||t[j]!=t[j+1]){a=max(a,j-i);i=j+2;}}a=max(a,j-i);i=1,j=1;for(;j<n;j+=2){if(j==n-1||t[j]!=t[j+1]){a=max(a,j-i);i=j+2;}}a=max(a,j-i);cout<<a<<'\n';return0;}