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

lsmCC

#include <bits/stdc++.h>
using namespace std;
int n;
const int N=101;
string a[N];
int main()
{
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        int pos=-1;
        int cnt=0,ans=0;
        string c="ab";
        string d="ba";
        while((pos=a[i].find(c,pos+1))!=-1)
        {
            cnt++; //
        }
        while ((pos=a[i].find(d,pos+1))!=-1)
        {
            ans++;
        }
    
        if(a[i].size()==1)cout<<a[i]<<endl;
        else
        {
            if(cnt!=ans)
            {
                a[i][0]='b';
                cout<<a[i]<<endl;
            }
            else cout<<a[i]<<endl;
          
            

        }
        
        
    }
    



}

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-11-13 00:57:43

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

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

#include <iostream>#include <string>using namespace std;int main() {    int n;    const int N = 101;    string a[N];    cin >> n;    for (int i = 0; i < n; i++) {        cin >> a[i];    }    for (int i = 0; i < n; i++) {        int cnt_ab = 0, cnt_ba = 0;        for (int j = 0; j < a[i].size() - 1; j++) {            if (a[i][j] == 'a' && a[i][j + 1] == 'b') {                cnt_ab++;            }            if (a[i][j] == 'b' && a[i][j + 1] == 'a') {                cnt_ba++;            }        }        if (a[i].size() == 1) {            cout << a[i] << endl;        } else {            if (cnt_ab != cnt_ba) {                a[i][0] = 'b';            }            cout << a[i] << endl;        }    }    return 0;}

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

跳转到最佳答案楼层

isdkz

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

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

下面是修改后的代码：

#include <bits/stdc++.h>
using namespace std;

int n;
const int N=101;
string a[N];

// KMP算法中的next数组计算函数
vector<int> getNext(string pattern) {
    int m = pattern.size();
    vector<int> next(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[ i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[ i] == pattern[j]) {
            j++;
        }
        next[ i] = j;
    }
    return next;
}

// KMP算法
int kmp(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> next = getNext(pattern);
    int cnt = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[ i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[ i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            cnt++;
            j = next[j - 1];
        }
    }
    return cnt;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[ i];
    }
    for (int i = 0; i < n; i++) {
        int cnt_ab = kmp(a[ i], "ab");
        int cnt_ba = kmp(a[ i], "ba");
        if (a[ i].size() == 1) {
            cout << a[ i] << endl;
        } else {
            if (cnt_ab != cnt_ba) {
                a[ i][0] = 'b';
                cout << a[ i] << endl;
            } else {
                cout << a[ i] << endl;
            }
        }
    }
}

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

Mike_python小

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

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

#include <iostream>#include <string>using namespace std;int main() {    int n;    const int N = 101;    string a[N];    cin >> n;    for (int i = 0; i < n; i++) {        cin >> a[i];    }    for (int i = 0; i < n; i++) {        int cnt_ab = 0, cnt_ba = 0;        for (int j = 0; j < a[i].size() - 1; j++) {            if (a[i][j] == 'a' && a[i][j + 1] == 'b') {                cnt_ab++;            }            if (a[i][j] == 'b' && a[i][j + 1] == 'a') {                cnt_ba++;            }        }        if (a[i].size() == 1) {            cout << a[i] << endl;        } else {            if (cnt_ab != cnt_ba) {                a[i][0] = 'b';            }            cout << a[i] << endl;        }    }    return 0;}

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