To solve this problem, we need to count the number of even-length palindromic substrings in a given string. An even-length palindrome is centered between two characters and expands outward, so we can leverage this property to efficiently find all such substrings.

Approach

1. Even-Length Palindrome Property: An even-length palindrome has no central character; instead, it is centered between two characters. For example, "bb" is centered between indices 1 and 2 in the string "abba".
2. Center Expansion: For each possible center between characters (i, i+1) where i ranges from 0 to n-2 (n being the length of the string), we expand outward as long as the characters on both sides are equal. Each valid expansion corresponds to an even-length palindrome.
3. Count Valid Palindromes: For each center, count the number of valid expansions, which gives the number of even-length palindromes centered at that position. Sum these counts to get the total number of even-length palindromic substrings.

Solution Code

def count_even_palindromic_substrings(s):
    n = len(s)
    count = 0
    for i in range(n - 1):
        left = i
        right = i + 1
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

# Read input and output the result
print(count_even_palindromic_substrings(input().strip()))

Explanation

1. Initialization: We start with count set to zero to keep track of the number of even-length palindromic substrings.
2. Iterate Over Centers: For each center between characters (i, i+1):
   • Expand: We check if the characters at positions left (i) and right (i+1) are equal. If they are, we increment the count and expand further left and right.
   • Termination: The expansion stops when the characters are no longer equal or we go out of bounds of the string.
3. Result: The sum of all valid expansions gives the total number of even-length palindromic substrings.

This approach efficiently counts even-length palindromic substrings with a time complexity of O(n²) (where n is the length of the string) and space complexity of O(1) (excluding input storage), which is optimal for most practical purposes. This method ensures we correctly find all even-length palindromic substrings by leveraging the center expansion technique.

作者声明:本文包含人工智能生成内容。