robinmbstu11's blog

By robinmbstu11, 10 years ago, In English

How can i print all palindrome from a string ? string length is <=10^6. If there is an algorithmic solution or any solution or any Technic please share it. Thanks in advance. :)

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can try Manacher's algo for finding all palindromes:

»
10 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Printing all of them will be quite hard as for example if the string is "aaa...aaa" then every substring is a palindrome, also printing the length of each palindrom and the position in the string where it starts is also quite hard as if every substring is a palindrome then there can be, if all the letters are the same, (N*(N+1))/2 palindromes, and that can be about 5*10^11. Counting all the palindromes is a bit easier, you can do it as follows:

As there are palindromes of even length and palindromes of odd length, and we want to count them all (not considering them as different cases) we will change the string in the following way: if the string is "abcda" then we change it to ".a.b.c.d.a.". Then we will find the longest odd length palindrome centered at each letter (odd length palindromes in the original string) and the longest odd length palindrome centered at each dot (even length palindromes in the original string). Once we find the longest palindrome for each letter then if s[i] is a letter and its longest palindrome has length 4t-1 (*1) then we have t palindromes centered at that letter in the original string (it's not hard to prove this) and if s[i] is a dot and its longest palindrome has length 4t+1 (*2) then we have t palindromes centered at that dot in the original string (the dot isn't in the original string but if for example, the palindrome is ".a.a." in the original string it matches "aa").

Now our only task is to find the longest odd length palindrome centered at each character in the new string. We can use the following algorithm that is linear:

int longest[N]; // N is the length of the modified string
memset(longest,0,sizeof(longest)); // we fill longest with 0s
int center = 0, last = 0; // (center,last) represents the palindrome centered at center that ends at last, we store the value with the greatest value of last here
for(int i=1;i<N;i++) //we start at 1 because there are no non-trivial palindromes with center at the first character
{
    if(last > i)
        longest[i] = min(longest[center-(i-center)],last-i);
    /*
        Try to prove that this if is correct by yourself. See that j = center-(i-center) is the symmetric of i with center as the point of symmetry. Then the longest palindrome centered at j that lies between the limits of the palindrome centered at center, is also a palindrome centered at i. I know this is quite confusing, so try proving it yourself.
    */
    while(i+longest[i]+1 < N && i-longest[i]-1 >= 0 && S[i+longest[i]+1] == S[i-longest[i]-1])
        longest[i]++;
    // We try to make the palindrome as long as possible.
    if(i+longest[i] > last)
    {
        last = i+longest[i];
        center = i;
    }
    // we update (center,last)
}
for(int i=0;i<N;i++)
    longest[i] = 2*longest[i]+1; // this is because longest stored only the length of half of the palindrome

Now you just need to count the number of palindromes centered at each character and you solve the problem.

(*1) As the borders of the palindromes will be dots, if the center is a letter the length will be 3 mod 4, for example, ".a." or ".a.b.a.", and so on. (*2) Same as (*1), the palindromes will be ".a.a.", ".a.b.b.a." and so on, so the length will always be 1 mod 4.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    And this comment has -9 because...?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also try palindromic tree. This concept also helps you to solve some interesting problems related to palindromes. For more details Link