string - 平方子序列

Question

如果一个字符串可以通过连接相同字符串的两个副本获得，则该字符串称为方字符串。例如，“abab”、“aa”是方串，而“aaa”、“abba”则不是。给定一个字符串，该字符串有多少个子序列是方串？字符串的子序列可以通过从其中删除零个或多个字符并保持剩余字符的相对顺序来获得。子序列不必是唯一的。

例如字符串 'aaa' 将有 3 个正方形子序列

Answer 1

观察 1：方串的长度总是偶数。

观察 2：长度为 2n (n>1) 的每个正方形子序列是两个较短子序列的组合：长度为 2(n-1) 的子序列和长度为 2 的子序列之一。

首先，找到长度为 2 的子序列，即字符串中出现两次或多次的字符。我们称这些对。对于每个长度为 2（1 对）的子序列，记住序列中第一个和最后一个字符的位置。

现在，假设我们有所有长度为 2(n-1) 的子序列，并且我们知道每个字符串中第一部分和第二部分的开始和结束位置。我们可以使用观察 2 找到长度为 2n 的序列：

遍历所有长度为 2(n-1) 的子序列，找到其中第一项位于第一部分的最后位置和第二部分的第一个位置之间且第二项位于第二部分的最后位置。每次找到这样的一对时，将其与当前长度为 2(n-2) 的子序列组合成一个新的长度为 2n 的子序列。

重复最后一步，直到不再找到新的正方形子序列。

Answer 2

伪代码：

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;
        }
    }
}

Answer 3

这是使用 LINQ 的解决方案：

IEnumerable<string> input = new[] {"a","a","a"};

// The next line assumes the existence of a "PowerSet" method for IEnumerable<T>.
// I'll provide my implementation of the method later.
IEnumerable<IEnumerable<string>> powerSet = input.PowerSet();

// Once you have the power set of all subsequences, select only those that are "square".
IEnumerable<IEnumerable<string>> squares = powerSet.Where(x => x.Take(x.Count()/2).SequenceEqual(x.Skip(x.Count()/2)));

Console.WriteLine(squares);

这是我的 PowerSet 扩展方法，以及 PowerSet 所需的“选择”扩展方法：

public static class CombinatorialExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> Choose<T>(this IEnumerable<T> seq, int k)
    {
        // Use "Select With Index" to create IEnumerable<anonymous type containing sequence values with indexes>
        var indexedSeq = seq.Select((Value, Index) => new {Value, Index});

        // Create k copies of the sequence to join
        var sequences = Enumerable.Repeat(indexedSeq,k);

        // Create IEnumerable<TypeOf(indexedSeq)> containing one empty sequence
        /// To create an empty sequence of the same anonymous type as indexedSeq, allow the compiler to infer the type from a query expression
        var emptySequence =
            from item in indexedSeq
            where false
            select item;
        var emptyProduct = Enumerable.Repeat(emptySequence,1);

        // Select "Choose" permutations, using Index to order the items
        var indexChoose = sequences.Aggregate( 
            emptyProduct,
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where accseq.All(accitem => accitem.Index < item.Index)
            select accseq.Concat(new[] { item }));

        // Select just the Value from each permutation
        IEnumerable<IEnumerable<T>> result = 
            from item in indexChoose
            select item.Select((x) => x.Value);

        return result;
    }

    public static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> seq)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
        for (int i=1; i<=seq.Count(); i++)
        {
            result = result.Concat(seq.Choose<T>(i));
        }
        return result;
    }
}

Answer 4

我最初导出所有可能的子序列，然后我将检查导出的子序列是否是正方形子序列

 import java.io.*;
 import java.util.*;

  public class Subsequence { 
  static int count;
  public static void print(String prefix, String remaining, int k) {

    if (k == 0) {
        //System.out.println(prefix);
        if(prefix.length() %2 == 0 && check(prefix) != 0 && prefix.length() != 0)
        {
            count++;
            //System.out.println(prefix);
        }
        return;
    }
    if (remaining.length() == 0) 
        return;

    print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
    print(prefix, remaining.substring(1), k);
 }


 public static void main(String[] args) 
 {
    //String s = "aaa";
    Scanner sc = new Scanner(System.in);
    int t=Integer.parseInt(sc.nextLine());
    while((t--)>0)
    {
        count = 0;
        String s = sc.nextLine();
        for(int i=0;i<=s.length();i++)
        {
             print("",s,i);
        }
        System.out.println(count);
     }
 }

 public static int check(String s)
 {
    int i=0,j=(s.length())/2;

    for(;i<(s.length())/2 && j < (s.length());i++,j++)
    {
        if(s.charAt(i)==s.charAt(j))
        {
                continue;
        }

        else
           return 0;
    }

    return 1;
}

}

Answer 5

import java.io.*;
import java.util.*;

public class Solution {
    /*
        Sample Input:
        3 
        aaa 
        abab 
        baaba

        Sample Output:
        3 
        3 
        6
    */
    public static void main(String[] args) {
        //Creating an object of SquareString class
        SquareString squareStringObject=new SquareString();
        Scanner in = new Scanner(System.in);
        //Number of Test Cases
        int T = in.nextInt();
        in.nextLine();
        String[] inputString=new String[T];
        for(int i=0;i<T;i++){
            // Taking input and storing in String Array
            inputString[i]=in.nextLine();
        }
        for(int i=0;i<T;i++){
            //Calculating and printing the number of Square Strings
            squareStringObject.numberOfSquareStrings(inputString[i]);
        }
    }
}
class SquareString{
    //The counter maintained for keeping a count of Square Strings
    private int squareStringCounter;
    //Default Constructor initialising the counter as 0
    public SquareString(){
        squareStringCounter=0;
    }
    //Function calculates and prints the number of square strings
    public void numberOfSquareStrings(String inputString){
        squareStringCounter=0;
        //Initialising the string part1 as a single character iterated over the length
        for(int iterStr1=0;iterStr1<inputString.length()-1;iterStr1++){
            String str1=""+inputString.charAt(iterStr1);
            String str2=inputString.substring(iterStr1+1);
            //Calling a recursive method to generate substring
            generateSubstringAndCountSquareStrings(str1,str2);
        }
        System.out.println(squareStringCounter);
    }
    //Recursive method to generate sub strings
    private void generateSubstringAndCountSquareStrings(String str1,String str2){
        for(int iterStr2=0;iterStr2<str2.length();iterStr2++){
            String newStr1=str1+str2.charAt(iterStr2);
            if(isSquareString(newStr1)){
                squareStringCounter++;
            }
            String newStr2=str2.substring(iterStr2+1);
            generateSubstringAndCountSquareStrings(newStr1,newStr2);
        }
    }
    private boolean isSquareString(String str){
        if(str.length()%2!=0)
            return false;
        String strPart1=str.substring(0,str.length()/2);
        String strPart2=str.substring(str.length()/2);
        return strPart1.equals(strPart2);
    }
}