正方形子序列

Question

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

例如字符串"aaa"将具有3个平方子序列

- Avinash

---

你的问题是什么？除了“请帮我做作业”以外？ - Greg Hewgill

如果这是一个作业问题，请标记为“作业”，并说明您已经采取了哪些方法来解决问题。（如果这不是一个作业问题，我很抱歉。）谢谢！ - ninjagecko

我在编程挑战中遇到了这个问题...我觉得它很有趣，但是无法解决它... - Avinash

这个问题最初在interviewstreet.com上陈述，有更多的例子。 - Colonel Panic

重要的是，原始的挑战要求提供一个“高效”的解决方案，“字符串S可能有多达200个字符”。 - Colonel Panic

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的子序列。

重复上述步骤，直到找不到新的正方形子序列为止。

- Jeffrey Sax

---

看起来你的方法可能行得通...第二个观察结果似乎真的简化了问题...非常感谢！ - Avinash

供他人参考，这种通过将同一问题的较小情况的解决方案组合起来解决问题的技术被称为“动态规划”。它就像逆向运行的递归。 - Colonel Panic

抱歉..您能解释一下“每个长度为1的子序列”是什么意思吗？是字符串中的每个字符吗？谢谢。 - louis.luo

看起来你已经将“长度为1”的更新为“长度为2（1对）”。谢谢。 - louis.luo

你能详细说明一下第二点观察吗？我很难理解你在这里的意图是什么。 - TheEmeritus

这种方法是可行的，但我的Python实现在https://www.hackerrank.com/challenges/square-subsequences的一些测试用例上超时了。 - gsganden

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

- Ina

---

一个子序列需要是连续的。'abacb' 包含正方形子序列 'abab'。你的算法会错过这个。 - Jeffrey Sax

我们正在寻找正方形子序列...你的算法似乎在搜索子字符串，为什么你假设一个子字符串只能有一个正方形子序列？ - Avinash

Answer 3

我最初会推导出所有可能的子序列，然后检查这些子序列是否为正方形子序列。

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

}

- coder101

---

请给出所需空间的估计。 - greybeard

如果字符串非常长，它会占用太多的空间，我正在尝试寻找更好的解决方案，仍在努力中。 - coder101

Answer 4

这里有一个使用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;
    }
}

- mbeckish

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

- Biplob Manna