Square Subsequence

Question

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how many subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.The subsequence need not be unique.

eg string 'aaa' will have 3 square subsequences

Answer 1

Observation 1: The length of a square string is always even.

Observation 2: Every square subsequence of length 2n (n>1) is a combination of two shorter subsequences: one of length 2(n-1) and one of length 2.

First, find the subsequences of length two, i.e. the characters that occur twice or more in the string. We'll call these pairs. For each subsequence of length 2 (1 pair), remember the position of the first and last character in the sequence.

Now, suppose we have all subsequences of length 2(n-1), and we know for each where in the string the first and second part begins and ends. We can find sequences of length 2n by using observation 2:

Go through all the subsequences of length 2(n-1), and find all pairs where the first item in the pair lies between the last position of the first part and the first position of the second part, and the second item lies after the last position of the second part. Every time such a pair is found, combine it with the current subsequence of length 2(n-2) into a new subsequence of length 2n.

Repeat the last step until no more new square subsequences are found.

Answer 2

Psuedocode:

total_square_substrings <- 0

# Find every substring
for i in 1:length_of_string {

    # Odd strings are not square, continue
    if((length_of_string-i) % 2 == 1)
        continue;

    for j in 1:length_of_string {
        # Remove i characters from the string, starting at character j
        substring <- substr(string,0,j) + substr(string,j+1,length_of_string);

        # Test all ways of splitting the substring into even, whole parts (e.g. if string is of length 15, this splits by 3 and 5)
        SubstringTest: for(k in 2:(length_of_substring/2))
        {           
            if(length_of_substring % k > 0)
                continue;

            first_partition <- substring[1:partition_size];

            # Test every partition against the first for equality, if all pass, we have a square substring
            for(m in 2:k)
            {           
                if(first_partition != substring[(k-1)*partition_size:k*partition_size])
                    continue SubstringTest;
            }

            # We have a square substring, move on to next substring
            total_square_substrings++;
            break SubstringTest;
        }
    }
}