Palindrome substring 2 - MarisaOJ: Marisa Online Judge

Palindrome substring 2

Time limit: 1000 ms
Memory limit: 256 MB
Count the number of palindrome substrings of a given string $S$. A substring of $S$ is a string that can be obtained from $S$ by removing some (possibly zero) characters from the beginning of $S$ and some (possibly zero) characters from the end of $S$. ### Input - 1 line contains string $S$. ### Output - The number of palindrome substrings of $S$. ### Constraints - $1 \le |S| \le 10^5$. ### Example Input: ``` mima ``` Output: ``` 5 ```