解题思路:
开始直接使用暴力算法,两个嵌套循环进行搜索,时间复杂度为O(n^2),这意味着对于非常长的字符串,程序需要执行大量的计算,效率低下。
我们可以通过以下步骤改进这个算法:
1.预处理: 遍历一遍字符串,预处理并保存每一个字符出现的位置。
2.滑动窗口: 使用双指针的策略,一个指针在找到c1后开始,另一个寻找c2,这样可以在O(n)的时间复杂度内完成。
3.快速统计: 一旦找到一个c2,我们知道所有在c1和这个c2之间的字符都能形成一个有效的子串。我们可以快速计算在当前c2之后有多少个c2,从而快速增加计数。
这里是改进后的代码:
#include <stdio.h> #include <string.h> int main() { int k; scanf("%d", &k); char s[500001];// 多一个'\0' char c1, c2; scanf("%s %c %c", s, &c1, &c2); int len = strlen(s); // strlen的时间复杂度为O(n),这里预处理 long long count = 0; // 这里可能的子串数量可能非常大!要使用更大范围的整数类型(其余地方int就足够) int c2_instances[len]; // 存储c2字符出现的位置 int c2_count = 0; // c2字符的数量 int i; // 预处理c2字符出现的位置 for(i=0; i<len; ++i) { if (s[i]==c2) { c2_instances[c2_count++] = i; } } int j=0; // c2的索引 for(i=0; i<len; ++i) { if(s[i]==c1) { // 寻找从当前c1开始,第一个位置大于等于i + k - 1的c2 while(j<c2_count && c2_instances[j]< i+k-1) { ++j; } // 从当前c1开始,直到字符串末尾的c2都可以形成有效子串 count += c2_count-j; } } printf("%lld", count);// 输出匹配ll类型的count return 0; }
这个改进的代码的时间复杂度是O(n),其中n是字符串的长度。预处理步骤和滑动窗口遍历都只需要单次遍历字符串,因此大大减少了计算量,并有助于避免超时。
0.0分
8 人评分
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:721 |
C二级辅导-公约公倍 (C语言代码)浏览:2122 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:580 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:615 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:604 |
字符串比较 (C语言代码)答案错误????浏览:597 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:604 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:588 |
IP判断 (C语言代码)浏览:539 |
模拟计算器 (C语言代码)浏览:2300 |