1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int main() { int n, k; // [1] n-行驶状态字符串S的长度,k-需要统计的子串长度 cin >> n >> k; // [2] 输入字符串长度n和子串长度k string s; // [3] s-存储汽车行驶状态的字符串(仅包含F、B、L、R) cin >> s; // [4] 输入长度为n的行驶状态字符串S vector<string> c; // [5] c-存储所有从S中截取的长度为k的子串 // 截取所有长度为k的子串并存入数组c for(int i=0;i<=n-k;i++){ // [6] 遍历所有合法的子串起始位置(i最大为n-k,保证子串长度为k) string a=""; // [7] a-临时存储当前截取的长度为k的子串 for(int j=i;j<i+k;j++){ // [8] 从起始位置i开始,截取连续k个字符 a+=s[j]; // [9] 逐个拼接字符,构建当前长度为k的子串 } c.push_back(a); // [10] 将构建好的子串存入数组c } sort(c.begin(),c.end()); // [11] 对所有子串排序,使相同子串连续排列,便于统计重复次数 // 统计重复出现(次数>1)的子串数量 long long sum=0,count=1; // [12] sum-最终结果(重复子串的数量),count-记录当前子串的连续出现次数(初始为1) for(int i=1;i<c.size();i++){ // [13] 遍历排序后的子串数组,从第2个元素开始对比 if(c[i]==c[i-1]){ // [14] 若当前子串与前一个子串相同,计数+1 count++; }else{ // [15] 若当前子串与前一个不同,检查前一个子串的出现次数 if(count>1) sum++; // [16] 若前一个子串出现次数>1,计入统计结果 count=1; // [17] 重置计数,开始统计下一个子串的出现次数 } } if(count>1) sum++; // [18] 处理循环结束后最后一组子串(避免遗漏) cout<<sum; // [19] 输出重复出现的长度为k的子串数量 return 0; }
- 1
信息
- ID
- 1455
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者