[已解决]codeforcess上一道题超时了，应该怎么修改

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n;
   
4. const int N=101;
   
5. string a[N];
   
6. int main()
   
7. {
   
8.     cin>>n;
   
9.     string s;
   
10.     for(int i=0;i<n;i++)
    
11.     {
    
12.         cin>>a[i];
    
13.     }
    
14.     for(int i=0;i<n;i++)
    
15.     {
    
16.         int pos=-1;
    
17.         int cnt=0,ans=0;
    
18.         string c="ab";
    
19.         string d="ba";
    
20.         while((pos=a[i].find(c,pos+1))!=-1)
    
21.         {
    
22.             cnt++; //
    
23.         }
    
24.         while ((pos=a[i].find(d,pos+1))!=-1)
    
25.         {
    
26.             ans++;
    
27.         }
    
28.    
    
29.         if(a[i].size()==1)cout<<a[i]<<endl;
    
30.         else
    
31.         {
    
32.             if(cnt!=ans)
    
33.             {
    
34.                 a[i][0]='b';
    
35.                 cout<<a[i]<<endl;
    
36.             }
    
37.             else cout<<a[i]<<endl;
    
38.          
    
39.             
    
40. 
    
41.         }
    
42.         
    
43.         
    
44.     }
    
45.    
    
46. 
    
47. 
    
48. 
    
49. }

复制代码

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-11-13 00:57:43

这段代码中出现超时的问题主要是在字符串查找部分的逻辑，导致时间复杂度较高。为了提高效率，可以对字符串查找部分进行优化，同时简化冗余的逻辑。

以下是对代码的修改建议：

2. #include <iostream>
3. #include <string>
4. using namespace std;
6. int main() {
7.     int n;
8.     const int N = 101;
9.     string a[N];
11.     cin >> n;
12.     for (int i = 0; i < n; i++) {
13.         cin >> a[i];
14.     }
16.     for (int i = 0; i < n; i++) {
17.         int cnt_ab = 0, cnt_ba = 0;
18.         for (int j = 0; j < a[i].size() - 1; j++) {
19.             if (a[i][j] == 'a' && a[i][j + 1] == 'b') {
20.                 cnt_ab++;
21.             }
22.             if (a[i][j] == 'b' && a[i][j + 1] == 'a') {
23.                 cnt_ba++;
24.             }
25.         }
27.         if (a[i].size() == 1) {
28.             cout << a[i] << endl;
29.         } else {
30.             if (cnt_ab != cnt_ba) {
31.                 a[i][0] = 'b';
32.             }
33.             cout << a[i] << endl;
34.         }
35.     }
36.     return 0;
37. }

复制代码

这样修改后的代码应该能够避免超时问题，并且更加高效地统计子串出现的次数。

跳转到最佳答案楼层

isdkz

这段代码的问题在于使用了两个嵌套的while循环来遍历字符串中的子串，这种方法在字符串较长时会导致超时。为了解决这个问题，可以使用一个更高效的算法来统计字符串中特定子串出现的次数。

一个更高效的方法是使用KMP算法来在字符串中搜索子串的出现次数。KMP算法可以在O(n+m)的时间复杂度内完成搜索，其中n是主串的长度，m是模式串（子串）的长度。

下面是修改后的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n;
   
5. const int N=101;
   
6. string a[N];
   
7. 
   
8. // KMP算法中的next数组计算函数
   
9. vector<int> getNext(string pattern) {
   
10.     int m = pattern.size();
    
11.     vector<int> next(m, 0);
    
12.     for (int i = 1, j = 0; i < m; i++) {
    
13.         while (j > 0 && pattern[ i] != pattern[j]) {
    
14.             j = next[j - 1];
    
15.         }
    
16.         if (pattern[ i] == pattern[j]) {
    
17.             j++;
    
18.         }
    
19.         next[ i] = j;
    
20.     }
    
21.     return next;
    
22. }
    
23. 
    
24. // KMP算法
    
25. int kmp(string text, string pattern) {
    
26.     int n = text.size(), m = pattern.size();
    
27.     vector<int> next = getNext(pattern);
    
28.     int cnt = 0;
    
29.     for (int i = 0, j = 0; i < n; i++) {
    
30.         while (j > 0 && text[ i] != pattern[j]) {
    
31.             j = next[j - 1];
    
32.         }
    
33.         if (text[ i] == pattern[j]) {
    
34.             j++;
    
35.         }
    
36.         if (j == m) {
    
37.             cnt++;
    
38.             j = next[j - 1];
    
39.         }
    
40.     }
    
41.     return cnt;
    
42. }
    
43. 
    
44. int main() {
    
45.     cin >> n;
    
46.     for (int i = 0; i < n; i++) {
    
47.         cin >> a[ i];
    
48.     }
    
49.     for (int i = 0; i < n; i++) {
    
50.         int cnt_ab = kmp(a[ i], "ab");
    
51.         int cnt_ba = kmp(a[ i], "ba");
    
52.         if (a[ i].size() == 1) {
    
53.             cout << a[ i] << endl;
    
54.         } else {
    
55.             if (cnt_ab != cnt_ba) {
    
56.                 a[ i][0] = 'b';
    
57.                 cout << a[ i] << endl;
    
58.             } else {
    
59.                 cout << a[ i] << endl;
    
60.             }
    
61.         }
    
62.     }
    
63. }
    

复制代码

这样修改后的代码使用了KMP算法来统计字符串中 "ab" 和 "ba" 的出现次数，大大提高了效率，避免了超时问题。

Mike_python小

这段代码中出现超时的问题主要是在字符串查找部分的逻辑，导致时间复杂度较高。为了提高效率，可以对字符串查找部分进行优化，同时简化冗余的逻辑。

以下是对代码的修改建议：

2. #include <iostream>
3. #include <string>
4. using namespace std;
6. int main() {
7.     int n;
8.     const int N = 101;
9.     string a[N];
11.     cin >> n;
12.     for (int i = 0; i < n; i++) {
13.         cin >> a[i];
14.     }
16.     for (int i = 0; i < n; i++) {
17.         int cnt_ab = 0, cnt_ba = 0;
18.         for (int j = 0; j < a[i].size() - 1; j++) {
19.             if (a[i][j] == 'a' && a[i][j + 1] == 'b') {
20.                 cnt_ab++;
21.             }
22.             if (a[i][j] == 'b' && a[i][j + 1] == 'a') {
23.                 cnt_ba++;
24.             }
25.         }
27.         if (a[i].size() == 1) {
28.             cout << a[i] << endl;
29.         } else {
30.             if (cnt_ab != cnt_ba) {
31.                 a[i][0] = 'b';
32.             }
33.             cout << a[i] << endl;
34.         }
35.     }
36.     return 0;
37. }

复制代码

这样修改后的代码应该能够避免超时问题，并且更加高效地统计子串出现的次数。