Square Subsequences

This problem effectively involves a reduction to a relative of a classic DP problem: the Longest Common Subsequence.

First, let’s construct an algorithm to find the number of common subsequences between two strings, s₁ and s₂. We can develop a recursive formula for N(i,j) = the number of common subsequences in s₁[:i] and s₂[:j].

If s₁[i] ≠ s₂[j], this will be the number of common subsequences in s₁[:i-1] and s₂[:j] plus the number of common subsequences in s₁[:i] and s₂[:j-1]. This double counts the number of common subsequences in s₁[:i-1] and s₂[:j-1], so the proper expression is

If s₁[i] = s₂[j], we need to add to this count the number of common subsequences including these two elements. This number is one (the one-element subsequence) plus N(i-1,j-1) (each of those subsequences with these elements appended).

Now we can work out the number of square subsequences by dividing the string at each possible split point, and calculating the number of common subsequences in the two substrings. However, this will overcount the subsequences: For example, ab will be counted in the string abcdab in the splits (ab, cdab), (abc, dab), and (abcd, ab). To avoid this, we only count matching subsequences that use that last element of s₁. That is, we want N(i,j) - N(i-1,j).

Let’s work out the example of abcdab with this algorithm. First, by inspection, we see three square subsequences: aa, bb, and abab.

1. a, bcdab: Common subsequence: a.
2. ab, cdab: Common subsequences: ab, b. Note that a appears in both substrings, but is not counted since the first substring ends in b.
3. abc, dab: None.
4. abcd, ab: None.
5. abcda, b: None.

With 1 from step 1 and 2 from step 2 (conveniently enough), we get the total of three square subsequences we were expecting.

NUMBER = 1000000007

def solve_sub(string, size):
    s1 = string[:size]
    size1 = len(s1) + 1
    s2 = string[size:]
    size2 = len(s2) + 1
    N = [[0 for j in range(size2)] for i in range(size1)]

    for i in range(1, size1):
        for j in range(1, size2):
            if s1[i - 1] == s2[j - 1]:
                N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
            else:
                N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]

    return N[-1][-1] - N[-2][-1]

def solve(string):
    count = sum(solve_sub(string, i) for i in range(1, len(string)))
    return count % NUMBER

if __name__ == '__main__':
    import sys
    _ = sys.stdin.readline()
    for line in sys.stdin:
        print(solve(line.strip()))