string - 正方形のサブシーケンス

Question

文字列は、同じ文字列の2つのコピーを連結して取得できる場合、正方形の文字列と呼ばれます。たとえば、「abab」、「aa」は正方形の文字列ですが、「aaa」、「abba」はそうではありません。文字列が与えられた場合、文字列のサブシーケンスはいくつ正方形の文字列ですか？文字列のサブシーケンスは、0個以上の文字を削除し、残りの文字の相対的な順序を維持することで取得できます。サブシーケンスは一意である必要はありません。

たとえば、文字列'aaa'には3つの正方形のサブシーケンスがあります

Answer 1

観察1：正方形の文字列の長さは常に偶数です。

観察2：長さ2n（n> 1）のすべての正方形のサブシーケンスは、2つの短いサブシーケンスの組み合わせです。1つは長さ2（n-1）で、もう1つは長さ2です。

まず、長さ2のサブシーケンス、つまり文字列内で2回以上出現する文字を見つけます。これらのペアをと呼びます。長さ2（1ペア）のサブシーケンスごとに、シーケンスの最初と最後の文字の位置を覚えておいてください。

ここで、長さ2（n-1）のすべてのサブシーケンスがあり、文字列の最初と2番目の部分が開始および終了する場所がそれぞれわかっているとします。観測2を使用して、長さ2nのシーケンスを見つけることができます。

長さ2（n-1）のすべてのサブシーケンスを調べて、ペアの最初の項目が最初の部分の最後の位置と2番目の部分の最初の位置の間にあり、2番目の項目が2番目の部分の最後の位置。そのようなペアが見つかるたびに、それを長さ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に必要な「Choose」拡張メソッドです。

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