求助,超时,

B4039 [GESP202409 三级] 回文拼接

jinxiaohan @ 2024-12-20 19:50:35

超时,不知道是回文判断太慢还是找字串的问题。

#include<bits/stdc++.h>
using namespace std;
int l,ans,r;
string s;
bool check(int l,int r)
{
    int c[30];
    memset(c,0,sizeof(c));
    for(int i = 0;i <= (r-l)/2;i++)
        if(s[l+i] != s[r-i])return false;
    for(int i = l;i <= r;i++)
    {
        c[s[i] - 'a']++;
        if(c[s[i] - 'a'] > 2)return false;
    }
    return true;
}
int main()
{
    cin>>s;
    int len = s.length();
    for(int i = 0;i < len;i++)
        for(int j = i;j < len;j++)
            if(j - i <= 2*len && check(i,j))
                ans++;
    cout<<ans;
    return 0;
}

|