ABC433C 1122子串
大约 3 分钟字符串
ABC433C 1122子串
【算法标签】 字符串、枚举
【语法标签】 :string、for循环、while循环
二、算法思路
- 枚举字符串每一个下标 i 作为合法子串的起始位置(覆盖所有可能起点,不漏解);
- 对起点
i,向右连续查找与s[i]相同的字符,得到左半段最大连续长度L; - 右半段起始下标
r_start = i + L,判断剩余字符是否足够容纳长度为L的右半段,不足则跳过当前起点; - 校验从
r_start开始的连续L个字符全部相等; - 校验左半段数字恰好比右半段数字小 1,满足则总计数
cnt + 1; - 遍历完成后输出合法子串总数。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int cnt = 0;
int n = (int)s.size();
// 逐个遍历左侧起点 i
for (int i = 0; i < n; i++) {
char c1 = s[i]; // 取左段第一个字符
// 步骤1:从i往后找连续相同字符,算出左段长度L
int L = 0;
while (i + L < n && s[i + L] == c1) {
L++;
}
// 左段结束位置
int r_start = i + L;
// 剩余字符不足L,无法形成等长右段,直接跳过
if (r_start + L > n) continue;
// 步骤2:校验右半段全部字符相同
char c2 = s[r_start]; // 取右段第一个字符
bool ok = true;
for (int k = 0; k < L; k++) {
if (s[r_start + k] != c2) {
ok = false;
break;
}
}
// 步骤3:判断数字恰好大1 且右端字符全部相同
if (ok && (c2 - '0') - (c1 - '0') == 1) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}四、 复杂度
时间复杂度
外层循环遍历 个起点 ;
每个起点求 最坏 ;
校验右半段又嵌套循环 ;
整体最坏复杂度 。
适用范围与缺陷
- 小数据:字符串长度 可稳定通过;
- 大数据:字符串长度 时,平方级运算量极大,会直接超时;
- 重复冗余计算:同一连续字符段会被多次重复遍历校验,存在大量重复运算。
五、优化方向
采用分段预处理线性算法:
先把字符串相同的子串全部取出来存在一个数组中,
接下来遍历相邻两段,若满足数字差 ,则累加 min(左段长度,右段长度)
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
int n = S.size();
if (n < 2) {
cout << 0 << endl;
return 0;
}
long long ans = 0;
// 保存上一段的字符、长度
char pre_c = S[0];
int pre_len = 1;
// 保存当前段的字符、长度
char cur_c = S[0];
int cur_len = 1;
//上一段和当前段位相邻的两段,最终是要比较相邻的段
for (int i = 1; i < n; ++i) {
if (S[i] == cur_c) {
// 和当前段字符相同,当前段长度+1
cur_len++;
} else {
// 出现新分段:前一段(pre_c,pre_len) 和 当前段(cur_c,cur_len) 是相邻两段
if (cur_c == pre_c + 1) {
ans += min(pre_len, cur_len); // 从外向内有多个子串符号要求
}
// 更新当前段为新的前一段
pre_c = cur_c;
pre_len = cur_len;
//并重置当前段
cur_c = S[i];
cur_len = 1;
}
}
// 循环结束后,还要处理最后一组相邻两段
if (cur_c == pre_c + 1) {
ans += min(pre_len, cur_len);
}
cout << ans << endl;
return 0;
}