To solve this problem, we need to count the number of substrings of string ( S ) that are anagrams of any substring of string ( T ). An anagram of a substring means the substring has the same character frequency but possibly in a different order.

Approach

1. Preprocess String ( T ): For each possible length ( L ) (from 1 to the length of ( T )), compute the frequency of characters for all substrings of ( T ) of length ( L ). Store these frequency counts in a dictionary where the key is the length ( L ) and the value is a set of tuples representing the frequency counts of substrings of length ( L ). This helps in quick lookup later.
2. Process String ( S ): For each length ( L ) that exists in the preprocessed dictionary of ( T ), compute the frequency of characters for all substrings of ( S ) of length ( L ). Check if any of these frequency counts exist in the corresponding set from ( T ). If they do, increment the count of valid substrings.

Solution Code

def count_anagram_substrings(S, T):
    def get_freq_set(s, length):
        freq = [0] * 26
        # Initialize the first window
        for i in range(length):
            c = s[i]
            freq[ord(c) - ord('a')] += 1
        freq_set = set()
        freq_set.add(tuple(freq))
        # Slide the window over the string
        for i in range(length, len(s)):
            # Remove the leftmost character of the previous window
            left_char = s[i - length]
            freq[ord(left_char) - ord('a')] -= 1
            # Add the current character to the window
            curr_char = s[i]
            freq[ord(curr_char) - ord('a')] += 1
            freq_set.add(tuple(freq))
        return freq_set

    # Preprocess T to get frequency sets for all possible lengths
    T_freq = {}
    len_T = len(T)
    for L in range(1, len_T + 1):
        if L > len_T:
            continue
        freq_set = get_freq_set(T, L)
        if freq_set:
            T_freq[L] = freq_set

    # Count valid substrings in S
    count = 0
    len_S = len(S)
    for L in T_freq:
        if L > len_S:
            continue  # No substrings of S with this length
        # Compute frequency for substrings of S of length L
        freq = [0] * 26
        # Initialize first window
        for i in range(L):
            c = S[i]
            freq[ord(c) - ord('a')] += 1
        if tuple(freq) in T_freq[L]:
            count += 1
        # Slide the window over S
        for i in range(L, len_S):
            left_char = S[i - L]
            freq[ord(left_char) - ord('a')] -= 1
            curr_char = S[i]
            freq[ord(curr_char) - ord('a')] += 1
            if tuple(freq) in T_freq[L]:
                count += 1
    return count

# Example usage:
# S = "ab"
# T = "ba"
# print(count_anagram_substrings(S, T))  # Output: 3

Explanation

1. Preprocessing ( T ): The function get_freq_set computes the frequency of characters for all substrings of a given length. This is done using a sliding window technique to efficiently update the frequency count as we move from one substring to the next.
2. Processing ( S ): For each valid length (from ( T )), we again use a sliding window to compute the frequency of substrings of ( S ) and check if they exist in the preprocessed sets from ( T ). This ensures we count all valid substrings of ( S ) that are anagrams of any substring of ( T ).

This approach efficiently handles the problem with a time complexity of ( O(m^2 + nm) ) where ( m ) is the length of ( T ) and ( n ) is the length of ( S ), making it suitable for most practical cases. The use of sets ensures quick lookups, which is crucial for performance.

Example Walkthrough

For ( S = "ab" ) and ( T = "ba" ):

• Preprocessing ( T ): For ( L=1 ), the frequency sets are ({(1,0,...0), (0,1,...0)}) (for 'a' and 'b'). For ( L=2 ), the frequency set is ({(1,1,...0)}) (for "ba").
• Processing ( S ): For ( L=1 ), both "a" and "b" are valid, so count +=2. For ( L=2 ), "ab" is valid, so count +=1. Total count is 3, which is correct.

This solution effectively counts all valid substrings and handles edge cases like empty strings or no valid substrings. It is efficient and easy to understand.

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