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. :)
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
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. :)
Name |
---|
You can try Manacher's algo for finding all palindromes:
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:
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.
And this comment has -9 because...?
You can also try palindromic tree. This concept also helps you to solve some interesting problems related to palindromes. For more details Link