The Joel on Software Discussion Group (CLOSED)

Something more challenging.

What is the complexity of finding the longest pallindrome in a string with n number of characters?

NO GOOGLE PLEASE!!!

Isn't it just O(n)?  Or O(n/2)?

Determining whether a string is palindrome is o(n) operations.

Finding longest palindrome in a string is dfferent.

Upper bound (simplistic):
A string of character N contains
 1 string with character N
 2 string with Character (N - 1)
 ...
 N string with character 1

O(1*N+2*(N - 1) + 3* (N - 2) ... (N - 1)*2 + N*1) = O(???)

Here's a possibility (I haven't verified this though):

Given a string s, reverse it (call it rs). Now find the longest common substring between the 2 strings (s and rs).

The complexity of this is left as an exercise to the reader. :)

I see...  Is that O(n!)? ;)

At seems likely that any algorithm will be at least O(n^2). The palindrome could have any start position from 1 to n, and it could have any length from 1 to n. Thus to find the longest palindrome in an arbitrary string requires an n x n search by some means or another.

I should have said O(n^2) in the worst case. It is O(n) in the best case.

Here's my take.

Start on the first char. Search for the same char and check the string between the two is a palindrome - check for symmetry. The complexity for this is o(n log(n))

Then you need to do this for every char in the string for decreasing n.

The overall complexity is probably o(n^2 log(n)) similar to an np complete problem.

"NO GOOGLE PLEASE!!!"

What is this, a quiz?  On a Friday?

Is it just me, or does this sound like a homework or quiz problem?

There is no point:)

But don't you think this is more interesting than talking about how to implement the algorithm in C and how to use char[] and char* and other low level detail?

I am still waiting for someone's comment.

Ok, I didn't clarify that much. It is not as straight-forward as it sounds. The question was to find all the occurances of the longest pallindromes in a given string and replace each occurance with a given word. However, all characters were to be treated equally. So, in the string,

mom and dad went to the party

there would be three pallindromes:
mom
[space]dad[space]
t[space]t (between went and to)


Similarly the string,

,,,, malayalam ,,,,

would all be one single occurance of a pallindrome.

Thanks for the correction in the spelling of pallindrome. And my tutorial was not about explaining the piece of code I wrote. It was about why I had taken a pointer to a pointer instead of a single-pointer.

PS: I didn't read that interesting comment that was deleted you say. What did it say?

Finding palindromes is very simple using a different view of the matter.

Iterate over all the characters in the input text. Then comes the second and interesting part. Then assume that this character is the *middle* of the palindrome. So all you have to do is check the characters to its left and right etc. The third step is similar, but for even numbered palindromes: if this character and the next one are equal then inspect the characters to the left and the right of this pair, etc.

Obviously this is O(n^2) but simple to program and prove correct and good average time performance.

Karel, you are right, but not fully. I had tried this approach also. It will work all the time, but since you have to find the LARGEST OUTERMOST palindrome, it will fail when you have discovered a two characters that do not match but are inside a larger palindrome.

suppose you have a string like this:

moonoomdd ddmoonoom

You start with the second char 'o' and see if it has the same characters around it. The chars around it are 'm' on the left and 'o' on the right. So you move on, saying, "this can't be the center of a palindrome."

Then you traverse until you reach n, the fourth character in that string above, and this has an 'o' each surrounding it, and so you move more towards the extremes and you see it has 'oo' on each side and when you move more, you see it has 'moo' and 'oom' around it. It's all fine till here, but when you go to the next level, you see it has no character to the left a 'd' to the right. So you surmise that moonoom must be the first occurance of the largest pallindrome. But if you look closer, you'll see that in my question, the whole of the string is the largest occurance of such a palindrome.

Where are the giants who called me a kid, if people are thinking about in in more than a single try even after I have the code?



Here is what I did as a trial before I arrived at the final code. This code does exactly what you're saying.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_LEN 1000

int ReplacePallindromes(char**, char*);

int main(void)
{

char c, *InStr, *ReplaceWith;
int i;

c=' ';
i=0;

InStr=(char*)malloc(sizeof(char)*(MAX_LEN+1));
if(InStr==NULL) return -1;
ReplaceWith=(char*)malloc(sizeof(char)*(MAX_LEN+1));
if(ReplaceWith==NULL) return -1;

printf("\nEnter a string (1000 characters maximum): ");
while((c=getchar())!=EOF && c!='\n' & i<=MAX_LEN) InStr[i++]=c;
InStr[i]=0;

c=' ';
i=0;
printf("\n\nEnter the string that you wish to replace \npallindromes with (1000 characters maximum): ");
while((c=getchar())!=EOF && c!='\n' & i<=MAX_LEN) ReplaceWith[i++]=c;
ReplaceWith[i]=0;


if(ReplacePallindromes(&InStr, ReplaceWith)==0)
{
    printf("\nThe modified string is:\n\n  %s", InStr);
}
else
{
    printf("An error occured. The program will now end.");
    free(InStr);
    free(ReplaceWith);
    return -1;
}
    free(InStr);
    free(ReplaceWith);
return 0;
}

int ReplacePallindromes(char **InStr, char *ReplaceWith)
{

unsigned int Len;
unsigned int LenReplaceWith;
unsigned int MatchFound;
char *NewString;
int i;
int j;
int Counter;
int k;


if (*InStr==NULL || ReplaceWith==NULL) return -1;
if (*ReplaceWith==0) return -1;

MatchFound=0;
LenReplaceWith=strlen(ReplaceWith);
Len=strlen(*InStr);
if (Len<2) return -1;

for(i=0; i<=Len-2; i++)
{
    j=i+1;
    Match:
    if (*((*InStr)+i) == *((*InStr)+j))
    {
        MatchFound=1;
        //Look for an outer pallindrome
        if((i-1)>=0 && ((j+1)<Len))
        {
            i--;
            j++;
            goto Match;
        }
        else if((i-1<0 && j+1<Len) || (i-1>=0 && j+1>Len))
        {
            //This is the largest pallindrome. Replace it.
            *NewString=NULL;
            NewString=(char*)malloc(sizeof(char)*(Len-(j-i+1)+LenReplaceWith+1));
            for(Counter=0; Counter<(Len-(j-i+1)+LenReplaceWith+1); Counter++)
                *(NewString+Counter)=0;

            for(Counter=0;Counter<=i-1;Counter++)
                *(NewString+Counter)=*((*InStr)+Counter);

            for(Counter=0;Counter<LenReplaceWith;Counter++)
                *(NewString+i+Counter)=*(ReplaceWith+Counter);

            for(Counter=j+1, k=0; Counter<Len; Counter++, k++)
            {
                if(i>0)
                {
                    *(NewString+i-1+LenReplaceWith+k)=*((*InStr)+Counter);
                }
                else
                {
                    *(NewString+LenReplaceWith+k)=*((*InStr)+Counter);
                }
            }
            *(NewString+i+LenReplaceWith+k)=0;

            free(*InStr);
            Len=strlen(NewString);
            *InStr=(char*)malloc(sizeof(char)*(Len+1));
            if((*InStr)==NULL) return -1;
            strcpy(*InStr, NewString);
            free(NewString);

            i=i-1+LenReplaceWith;
            j=i+1;

            MatchFound=0;
        }
        else if(i-1<0 && j+1==Len)
        {
            //The whole thing is one big pallindrome
            free(*InStr);
            *InStr=(char*)malloc(sizeof(char)*(LenReplaceWith+1));
            if(*InStr==NULL) return -1;
            strcpy(*InStr, ReplaceWith);
            return 0;
        }
    }
    else
    {
        if(MatchFound==1)
        {
            //Pallindrome found at i-1 and j+1
            i++; j--;
            //Now the pallindrome is from bounds i to j, including both i and j
            *NewString=NULL;
            NewString=(char*)malloc(sizeof(char)*(Len-(j-i+1)+LenReplaceWith+1));
            for(Counter=0; Counter<(Len-(j-i+1)+LenReplaceWith+1); Counter++)
                *(NewString+Counter)=0;

            for(Counter=0;Counter<=i-1;Counter++)
                *(NewString+Counter)=*((*InStr)+Counter);

            for(Counter=0;Counter<LenReplaceWith;Counter++)
                *(NewString+i+Counter)=*(ReplaceWith+Counter);

            for(Counter=j+1, k=0; Counter<Len; Counter++, k++)
            {
                if(i>0)
                {
                    *(NewString+i+LenReplaceWith+k)=*((*InStr)+Counter);
                }
                else
                {
                    *(NewString+LenReplaceWith+k)=*((*InStr)+Counter);
                }
            }
            *(NewString+i+LenReplaceWith+k)=0;

            free(*InStr);
            Len=strlen(NewString);
            *InStr=(char*)malloc(sizeof(char)*(Len+1));
            if((*InStr)==NULL) return -1;
            strcpy(*InStr, NewString);
            free(NewString);

            i=i-1+LenReplaceWith;
            //j+i+1;
        }
        MatchFound=0;
        //continue with the outer for loop. Fetch the next two characters
    }
}//End of for loop

return 0;

}//End of the function ReplacePallindromes

Presumably, when you say "The question was to find all the occurances of the longest pallindromes in a given string and replace each occurance with a given word", you mean "replace each occurance with as much of a given word as will fit".

Two questions:

(1) What happens when the word isn't long enough to cover the longest palindromes?

(2) What happens when some of the longest palindromes overlap? i.e. "corroccor" - two longest palindromes are "corroc" and "roccor"

Hello S.C.

For the record, I did not call names. I reacted to earlier postings in this thread that proposed e.g. finding the largest common substring in the input and its reverse, or taking a character from the input as the start for a potential palindrome and look for matching ends and determine whether they span a palindrome. I did not spell out your code in the other thread, it is perfectly possible that you did what I proposed.

I gave just an outline for the algorithm. I thought that it was obvious that one must iterate over all characters in the input text and determine the largest palindrome of which this/these character (pair) is the center and keep record of the longest thus found. Otherwise your comment is correct.

My C++ is not good enough to comment on that.

O(n^2) is easy, just check each character (or gap between characters, so to speak) in turn for being at the middle of a palindrome. This is O(n^2) in the worst case and O(n) in the best case (which will be most of the time, given that most strings don't contain many palindromes at all). Google says that there is infact a guaranteed O(n) algorithm, which relies on first building up a suffix tree for the string in O(n) operations, and then using that to search for palindromes using another O(n) algorithm.

I was hoping for a simple O(n) stack-based algorithm but the one I came up with failed in some awkward special cases :( needs something cleverer than that.

I should also say: finding the palindromes is the algorithmically interesting bit, replacing them with something else afterwards is just tedious busy-work tacked onto the end of the problem.

Hi Julian,

Nice and clear thinking. Cool!


>Presumably, when you say "The question was to find all the occurances of the longest pallindromes in a given string and replace each occurance with a given word", you mean "replace each occurance with as much of a given word as will fit".

No, I mean:

-Eat the largest palindrome occurance, whatever it's length. Remove it from the original string; and then

-Insert at that position in the original string, another string, whatever be the length of the string you have to insert there.


>(1) What happens when the word isn't long enough to cover the longest palindromes?

It does not matter what the length of the palindrome found be as compared to the length of the word to replace it. We just have to replace them.

> (2) What happens when some of the longest palindromes overlap? i.e. "corroccor" - two longest palindromes are "corroc" and "roccor"

In such a case, the first palindrome found would be "corroc", and hence it would be replaced with the new text. Then the searching would start at the new index after the last character of the replaced text, and hence "roccor" would not be found. For instance, the text to be replaced was, "cool", we'd have:

"corroccor"
"corroc" found in "corroc" "cor"
"corroc" replaced with "cool"
new string="coolcor"
No more palindrome found

Karel,

I did not imply that you called names. I was just suggesting that your algorithm is very near to the correct one. It was what I landed on just before the correct algorithm. In fact, it was landing on the correct algorithm for this problem that was difficult. Your algorithm is <EM>almost</EM> correct, but it is not correct. It is very tempting to go into that algorithm and fail and realize that it is <EM>almost</EM> correct but not fully correct. It will desert us in the middle, when we meet a string like I described above. But it was a very intelligent guess.

That "giant comment thing" was to those who pulled me down. All big talk, no show.

Sathyaish, you are wrong.  Karel's algorithm is correct.  In your example, you claimed that when Karel gets to the first "n", he'll decide he's found the longest palindrome.  But that's not Karel's algorithm.  Karel will remember the 7-character palindrome centered on the first "n" as the longest so far, but then he'll carry on and eventually will consider the space as the center and find that the whole string is palindromic.

BTW, Karel doesn't have to find the largest "outermost" palindrome.  The question was "What is the complexity of finding the longest pallindrome in a string with n number of characters?"  The problem doesn't say which of several longest palindromes to find, so any of them will suffice.  Obviously if the whole string is a palindrome, it's the longest, but Karel's algorithm will correctly find the whole string when appropriate.

Here's the solution written in prolog, but because of the declarative nature of prolog, it doesn't shed light on the complexity of runnning time.  It's got some XSBisms, so you might need to change some predicates to fit in with your prolog.

:- import append/3 from basics.
:- import length/2 from basics.

find_longest_palindrome(P) :-
    atom(P), atom_chars(P,L),
    all_palindromes(L,Out), longest(X,Out),
    write('Longest palindrome: '), writeln(X).

all_palindromes(L,Out) :-
    findall(X, context(X,L,[]),Out).

longest(X,L) :- longest(X,[],L).

longest(X,X,[]).
longest(X,Current,[L1|Lrest]) :-
    length(L1,N),
    length(Current,M),
    (N > M -> longest(X,L1,Lrest) ;
              longest(X,Current,Lrest)).

context(Out) -->
    anyplus(_), palindrome(Out) |
    palindrome(Out), anyplus(_) |
    anyplus(_), palindrome(Out), anyplus(_) |
    palindrome(Out).

% The heart of the program
palindrome(Out) -->
    any(X), palindrome(O), [X],
        {append([X],O,I), append(I,[X],Out)} |
    any(X), [X], {Out = [X,X]} |
    any(X), any(Y), [X], {Out = [X,Y,X]}.

any(X) --> [X], {atom(X)}.
anyplus([X]) --> any(X) |
    any(X1), anyplus(X2), {append([X1],X2,X)}.

A little explanation:

First it finds _all_ palindromes of length 2 or greater (it doesn't get tripped up by overlapping), then it searches the list of all palindromes for the longest palindrome and outputs that.

Gotta love definite clause grammars :)

Karel is right, his algorithm, with small modifications (to work for both abba, abcba) would have o(n log(n))

I thought this was what Karel said:

>Then assume that this character is the *middle* of the palindrome. So all you have to do is check the characters to its left and right etc. The third step is similar, but for even numbered palindromes: if this character and the next one are equal then inspect the characters to the left and the right of this pair, etc.


If you were to find just palindromes with equal emphasis on all characters including punctuation, this would work, but if you had to determine the center of the longest palindrome, you would not have n iterations, but more, because in such a case, even if you found a center of a valid palindrome, you'd have to keep the palindrome in memory and search for the next center of a larger one. And if you didn't find one, you'd have to come back to the position just after the first palindrome you found ends.

Of course, Karel's solution was not about finding the largest one, so in a way, you're right. It is a correct solution.

>O(1*N+2*(N - 1) + 3* (N - 2) ... (N - 1)*2 + N*1) = O(???)


Rick, I forget now but I learnt this in XII standard maths. It looks like some binomial theorum (or exponential series, I may be wrong) excercise. I'd love to go back to my XII maths book again tonight and come up with an answer tomorrow. Yummy! I love that. Cool!

To others, please don't answer till tomorrow, until I've given up.

I couldn't find my book last night. One more day, please.

Karel's algorithm is exactly right, and needs no modification.

For fun, I programmed exactly this algorithm over the weekend as a fairly short C program.

My program produces the following output:

Some palindromes include: radar; able was I, ere I saw Elba; and tar rat.
=> Longest palindrome has length 19
Some palindromes include: radar; XXXX XXX X, XXX X XXX XXXX; and tar rat.

Surely no palindromes here?
=> No palindromes.

Redder at the front of it
=> Longest palindrome has length 6
XXXXXX at the front of it

At the back of it, redder
=> Longest palindrome has length 6
At the back of it, XXXXXX

Ground wave radar evades detection.
=> Longest palindrome has length 5
Ground wave XXXXX evades detection.

I think a palindrome could be quite short.
=> Longest palindrome has length 1
X think a palindrome could be quite short.

moonoomdd ddmoonoom
=> Longest palindrome has length 18
XXXXXXXXX XXXXXXXXX

In particular note that a palindrome should consist of whole words only, and that we should ignore punctuation when searching. So, for example, "ave radar eva" should not be reported in the fifth example.

Ian, some modifications are required:

"Do geese see God? "
"Dennis sinned"

The first palindrome is symmetrical around the middle e.

The second one has no middle letter, it is symmetrical around the double s in the middle.

What the algorithm should check is if the next or second next chars are the same with the current(ignoring case and space).

Do geese see God?
=> Longest palindrome has length 13
XX XXXXX XXX XXX?

Dennis sinned
=> Longest palindrome has length 12
XXXXXX XXXXXX

I made no changes to my code (which is Karel's algorithm exactly). What modifications are required?

Two simplifications are possible in the algorithm I presented. If a palindrome should not be sensitive to punctuation, then drop the punctuation from the input text *before* the searching. This greatly simplifies the most complex part of the algorithm.  However, be aware that the result thus obtained should be transformed back to the form where it had its punctuation. That should not be too difficult though.

The second simplification involves adding two different sentinel values at either side of the input text before the searching begins. These values must be unique in the entire resulting text string. Since they are unique, they can never be part of any palindrome. Therefore, they act as a very simple stopping criterion. Of course the outer iteration should now start at low+1 and stop at high-1.

I thought about removing the punctuation before searching, but I saw two problems: (1) It is not that trivial to remember where the punctuation went so as to put it back again afterwards; (2) You need the punctuation to identify word boundaries when searching.

On sentinel values: In C there is a natural \0 as a sentinel at the end, but not at the beginning. To put one at the front requires allocating new memory and copying the input string. I preferred just to do a pointer value comparison for the end points, and that way I could search the input string in place without needing to do any copying or mallocing. (The input text could be large; copying it just to put a sentinel at the front is not necessarily efficient.)

Ok, I think I got the answer last night. I searched for my Math  book and found it too. I rummaged through logarithmic series,  exponential series, binomial theorum, mathematical induction,  but didn't find a clue. Then I reasoned that each of the terms in  the polynomail were spread in an askewed symmetric normal  distribution. I took out my statistics book, but there was  nothing that told me to find the summation of the values in a  normal distribution given its variance. There was only kurtosis,  movements and skewness, interpolation and extrapolation. So I  stopped at that and tossed those books back to where they lay -  in my dusty shelf.

Here's what I got after many tries. I am definite it is the right  answer.

Q) N + 2(N-1) + 3(N-2) + 4(N-3) +...(N-1)*2 + N = ?
A:
If we open the brackets, we get:

=N + 2N - 2 + 3N - 6 + 4N - 12 + ...2N - 2 + N,

If we group the terms based on the degree of their variables,  we get:

= 2 {N+2N+3N+4N+....upto N/2 terms} -  2{2+6+12+20+30+42+...upto (N-2)/2 terms}

Taking 2 common, we get:

=2[{N+2N+3N+4N+....upto N/2 terms} -  {2+6+12+20+30+42+...upto (N-2)/2 terms}]

The first part, i.e. {N+2N+3N+4N+....upto N/2 terms} is an  Arithmetic Progression, where:

First Term (a) = N,
Factor (d) = N, and
No. Of Terms = N/2

The Sum of an AP with N terms is: N/2*{2a + d(N-1)}

Therefore,

The first part evaluates to,

=N/4*[2N+N{(N/2)-1}]

If we factorize this to the end, we get:

(N^2)(N+2)/8


Now, let's move to the second part:

={2+6+12+20+30+42+...upto (N-2)/2 terms}

Let the sum of these be called Sn, then,

Sn = 2+6+12+20+30+42+...[(N-2)/2]th term,

If we subtract the same expression from itself, but by  right-aligning it, that is,

Sn = 2+6+12+20+30+42+...[(N-2)/2]th term,
-Sn =    2+6+12+20+30+42+...[(N-2)/2]th term,
-------------------------------------------------------------
Sn-Sn = 2+4+6+8+10+12+....-[(N-2)/2]th term.
-------------------------------------------------------------

=> 0 = 2+4+6+8+10+12+....-[(N-2)/2]th term,
=> [(N-2)/2]th term = 2+4+6+8+10+12+....

Note that 2+4+6+8+10+12+.... is an AP where,

First Term (a) = 2,
Factor (d) = 2,
No. Of Terms = [(N-2)/2],

Therefore,

[(N-2)/2]th term = (n-2)/4 * [4 + 2{((N-2)/2) - 1}]

If we solve the right hand side, we get,

[(N-2)/2]th term = ((N^2) - 2N)/4

Let x = [(N-2)/2], then,

xth term = x*(N/2)=x*(x+1) = (x^2) + 1,

If the xth term is (x^2) + 1, then the sum of all x terms will be,

{x(x+1)(2x+1)}/6 + 1,

If we solve this by substituting back [(N-2)/2] in the place of x,  then get in terms of N, the answer of Part 2, which is:

{(N^3) - 3*(N^2) + 2N}/24,

Now the finale,

The answer = 2* {Part I - Part II}

2 * [ {(N^2)(N+2)/8} - {(N^3) - 3*(N^2) + 2N}/24 ],

which is,

=(N/12)* [ 2(N^2) + 9N -2 ]

Is this the correct answer?

Dunno. After reading all that I've forgotten what the question was.

O(1*N + 2*(N-1) + 3*(N-2) + 4*(N-3) + ....(N-1)*2 + N*1)=O(???)

Ian and Karel, you are right (again :-) no modifications are required. I didn't read carefully Karel's initial post. Complexity is indeed n^2.