Блог пользователя runtime_error

Автор runtime_error, 11 лет назад, По-английски

recently i have seen one problem on e-olimp.com.ua

this problem is about to find all 1 ≤ i < j ≤ n (n=string size) that a[i..j] is palindrome.

this is my solution:

#include<bits/stdc++.h>

using namespace std;

string pre_process(string s)
{
    int n=s.size();

    if(n==0) return "^$";

    string rev="^";
    for(int i=0;i<n;i++)
        rev+='#'+s.substr(i,1);
    rev+="#$";
    return rev;
}


long long  manacher(string s)
{
    string T=pre_process(s);
    int n=T.size();

    long long  answer=0;

    int *p=new int[n];

    int c=0,r=0;
    for(int i=1;i<n-1;i++)
    {
        int mirror=2*c-i;
        p[i]=(i<r)?min(p[mirror],r-i):0;

        while(T[i-1-p[i]]==T[i+1+p[i]])
            p[i]++;
        if(i+p[i]>r)
            c=i,r=i+p[i];


        if(p[i]>1)
            answer+=p[i]/2;
    }
    return answer;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin>>s;

    cout<<manacher(s)<<endl;

    return 0;
}

i use manacher's algorithm which time complexity is o(n),but i get TLE in last several test cases.

i know it can be solved whith suffix tree. Is is better than manacher?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't know the manacher's algorithm but i can presume that the reason of TLE is the using string objects. They aren't efficient enough for such manipulation. Try to replace strings with char arrays.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

I think this algorithm itself is fast enough. It's just your implementation that can be improved by not using C++ String and substr(...).