An advanced method for solving palindromes

The first is to give an example:

Find the number of palindromes in a string.

To get this problem, we know that the complexity of solving the palindrome by brute force is O(n)

i means the beginning character, j means the end character, and then judge whether it is a palindrome

O(n) for each operation, which is n^3, which is too big.

Then we find that the palindrome is symmetric, so if you start from the middle to find whether it is a palindrome, the time complexity can be reduced.So, the double pointer idea:

For i, there are two types, one lets (l=i, r=i) and the other lets (l=i-1, r=i), each judgment lets l--, r++, and then encountersThe string continues to execute and ++cnt, otherwise jump out.

What's good about it?

At this time, due to the symmetry of the string, the search for whether it is a string and the expansion of the search range are carried out at the same time. This has changed from the original j, k two layers to the idea of ​​continuous extension on both sides.

This is an improvement I can think of to take advantage of the symmetry of the palindrome.

The back is not what my stupid brain can think of..

Let's put it here first, there are several palindrome ideas.

But first of all, it needs to be explained that these things should be used. For example, finding the longest palindrome can also be used to find the length of the palindrome, and finding the palindrome at the end of X can also be used to find the palindrome.).

If you don't use it, you will learn in vain

Advanced idea of ​​palindrome: horse-drawn carriage, dp (jump search and non-jump search), palindrome tree.

The following content is slowly filled ()