11475 - Extend to Palindrome
Moderator: Board moderators
11475 - Extend to Palindrome
Hi!, its not the first time i see this problem, and its not the first time i dont see how to solve it... any hints? thanks! Eric.
Re: 11475 - Extend to Palindromes
Yes, i don't know too
There were problems like this an i solved them using DP, because the input size was less than 1000 but in this problem it's so huge.
There were problems like this an i solved them using DP, because the input size was less than 1000 but in this problem it's so huge.
Re: 11475 - Extend to Palindromes
Hint: Rolling hash might be a viable option here.
Re: 11475 - Extend to Palindromes
Knuth-Morris-Pratt algorithm is an option to consider if you're trying to solve this task.
Re: 11475 - Extend to Palindromes
Hi,
I use base N representation mod M, reading forward and backward, starting from
the last symbol. I keep get WA. I have tried many cases.
Help is appreciated! Thanks.
I use base N representation mod M, reading forward and backward, starting from
the last symbol. I keep get WA. I have tried many cases.
Help is appreciated! Thanks.
Code: Select all
Accepted... silly index error. Thanks!
Last edited by baodog on Mon Aug 04, 2008 11:00 am, edited 1 time in total.
Re: 11475 - Extend to Palindromes
@baodog:
Your code prints an extra unprintable character at the end of each line on my machine. But it looks otherwise ok.
@hamedv:
I'm curious about the O(n^2) DP you mentioned. The simple brute force way of solving this problem is also O(n^2). Could you please post an outline of your idea?
Your code prints an extra unprintable character at the end of each line on my machine. But it looks otherwise ok.
@hamedv:
I'm curious about the O(n^2) DP you mentioned. The simple brute force way of solving this problem is also O(n^2). Could you please post an outline of your idea?
Re: 11475 - Extend to Palindromes
I mean this:MAK wrote:@baodog:
Your code prints an extra unprintable character at the end of each line on my machine. But it looks otherwise ok.
@hamedv:
I'm curious about the O(n^2) DP you mentioned. The simple brute force way of solving this problem is also O(n^2). Could you please post an outline of your idea?
http://www.comp.nus.edu.sg/~stevenha/pr ... Palindrome
Re: 11475 - Extend to Palindromes
Thanks Hamedv. That is a much harder problem. The present problem asks that you only consider adding characters at the end of the string, which simplifies matters a lot.
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: 11475 - Extend to Palindromes
I think that is not that hard. because the length of the string is only 1000. So O(N^2) solution will be enough.
Re: 11475 - Extend to Palindromes
IMHO the idea behind the solution (and not the implementation) of this problem is somewhat simpler that the one Hamedv referred to.
Of course, what I find find hard (or easy) can quite naturally seem easy (or hard) to someone else
.
Of course, what I find find hard (or easy) can quite naturally seem easy (or hard) to someone else
![:-)](./images/smilies/icon_smile.gif)
Re: 11475 - Extend to Palindromes
i solved this using kmp string matching algorithm in 0.020 seconds
Learn to swim.
-
- New poster
- Posts: 2
- Joined: Thu Feb 05, 2009 5:44 pm
Re: 11475 - Extend to Palindromes
Anybody can help me?
I've use the KMP and I'm sure that my program run on the largest testcases. And it works.. but I have a TLE on my code.
I've use the KMP and I'm sure that my program run on the largest testcases. And it works.. but I have a TLE on my code.
Code: Select all
#include<iostream>
#include<stack>
using namespace std;
char text[100001], pat[100001];
int f[100001];
stack<char> tempS;
bool isPalindrome(char* T)
{
int i;
for(i=0;i<strlen(T)/2;i++)
if(T[i]!=T[strlen(T)-1-i])
return false;
return true;
}
void reverse(char T[], char* P)
{
int i;
char temp;
for(i=0;i<strlen(T);i++)
P[strlen(T)-1-i]=T[i];
P[strlen(T)]='\0';
}
void fFunction(char*P)
{
int i,j,m;
i=1;
j=0;
m=strlen(P);
while(i<=m-1)
{
if(P[j]==P[i])
{
f[i]=j+1;
i++;
j++;
}
else if(j>0)
j=f[j-1];
else
{
f[i]=0;
i++;
}
}
}
void KMPMatch(char* T, char*P)
{
bool done=false;
int i,j,m,trace=0,k;
i=0;
j=0;
while(i<=strlen(T) && !done)
{
m=strlen(P);
if(P[j]==T[i])
{
if(j==m-1)
{
cout<<text;
while(!tempS.empty())
{
cout<<tempS.top();
tempS.pop();
}
cout<<endl;
done=true;
}
i++;
j++;
}
else if (j>0)
{
trace=j;
j=f[j-1];
for(k=0;k<trace-j;k++)
{
tempS.push(P[strlen(P)-1]);
P[strlen(P)-1]='\0';
}
}
else
{
i++;
tempS.push(P[strlen(P)-1]);
P[strlen(P)-1]='\0';
}
}
}
int main()
{
int i;
while(cin>>text)
{
if(isPalindrome(text))
cout<<text<<endl;
else
{
reverse(text,pat);
fFunction(pat);
KMPMatch(text,pat);
}
}
return 0;
}
Re: 11475 - Extend to Palindromes
Try an input with a large string of the same character with a different character near the end.
e.g.
xxxxxx......xxxy
xxxxxx........xyxx
e.g.
xxxxxx......xxxy
xxxxxx........xyxx
-
- New poster
- Posts: 2
- Joined: Thu Feb 05, 2009 5:44 pm
Re: 11475 - Extend to Palindromes
yes, it works very fast, but it was TLE again when i submitted...
oh.. help me...![:-(](./images/smilies/icon_frown.gif)
oh.. help me...
![:-(](./images/smilies/icon_frown.gif)
Re: 11475 - Extend to Palindromes
Consider the dual of the problem: find the largest suffix of the input text that is a palindrome.
text = abB, where B is the reverse of b. Then textTEXT = abBbBA, then you find the longest tandem repeat...
This leads to O(nlogn) solution which gets TLE + MLE.
text = abB, where B is the reverse of b. Then textTEXT = abBbBA, then you find the longest tandem repeat...
This leads to O(nlogn) solution which gets TLE + MLE.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke