java - 方形子序列

Question

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

输入格式

第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个 case 都包含一个字符串 S。

输出格式

输出 T 行，每个测试用例一行，包含对 1000000007 求模的所需答案。

约束:1≤T≤20S 最多包含 200 个小写字符('a' - 'z')。

示例输入

3 
aaa 
abab 
baaba

示例输出

3 
3 
6

我的代码只通过了 2 个测试用例，因为大字符串的递归需要超过 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 1

基本思想:我们可以将所有可以从给定输入字符串派生的正方形序列排列成树状图 - 基本上是将几棵树合并为一棵树，并允许多个父树。这些树中的每棵树都有一个(局部)最长的可能正方形序列作为根，叶子都是长度为 2 的正方形子序列，可以从根序列中导出。现在找到所有可能的子序列的最简单方法是以任何给定的方式简单地遍历这棵树并计算节点数。由于很难找到给定输入的(局部)最长可能的正方形序列，我们使用另一个选项:从叶子开始并遍历到最长的序列。只需搜索所有可能的长度为 2 的正方形序列，就可以轻松找到这些。

方形序列之间的关系示例如下:

input: agbhbeiauzbib
longest sequences: abbabb and abiabi
childsequences of abbabb:
2x abab
bbbb

these sequences would have subsequences themselves of length 2

现在从理论到实践:
由于输入字符串中字符的位置与不同的两个序列相关(input: "aaa" sequences: 01->"aa" 02->"aa" 我们可以区分这些序列，尽管它们产生相同的字符串)，子序列可以表示为 List<Integer> .
现在第一步:找到所有可能的长度为 2 的正方形子序列:基本上我们需要做的就是找到长度为 2 的索引的所有排列，这样索引指向输入字符串中的等效字符。

private static List<List<Integer>> listDoubleSequences(String in)
{
    List<List<Integer>> result = new ArrayList<>();

    //map all characters to their indices in the inputstring
    HashMap<Character , List<Integer>> posMap = new HashMap<>();

    for(int i = 0 ; i < in.length() ; i++)
    {
        char c = in.charAt(i);

        if(posMap.get(c) == null)
            posMap.put(c , new ArrayList<>());

        posMap.get(c).add(i);
    }

    System.out.println(posMap);

    posMap.values().forEach(indices -> {
        //find all possible permutations with length 2
        for (int i = 0; i < indices.size(); i++)
            for (int j = i + 1; j < indices.size(); j++) {
                List<Integer> seq = new ArrayList<>();
                seq.add(indices.get(i));
                seq.add(indices.get(j));

                result.add(seq);
            }
    });

    System.out.println("Found double sequences:");
    result.forEach(l -> printSeq(in, l));

    return result;
}

既然找到了这些序列，剩下的就很简单了:长度为 n 的正方形子序列可以通过合并两个序列产生a和 b与 length_of_a + length_of_b = n成一个序列。由于所有的正方形序列都可以通过将序列与 length == 2 合并来导出，合并操作可以简化为仅使用长度为 2 的序列作为第二个参数。

private static List<Integer> merge(List<Integer> a , List<Integer> b)
{
    if(a.contains(b.get(0)) || a.contains(b.get(1)))
        return null;

    List<Integer> result = new ArrayList<>(a);

    result.addAll(b);
    Collections.sort(result);

    //check whether the indices from b have been inserted correctly
    //split the sequence into two parts of same length, now the position of b.get(0) 
    //in the first part must be equal to the position of b.get(1) in the second part
    if(result.indexOf(b.get(1)) - result.indexOf(b.get(0)) == result.size() / 2)
        return result;
    else
        return null;
}

因为任何有效的子序列 length > 2由许多带有 length == 2 的正方形序列组成, 我们可以通过简单地用 length 2 找到所有可能的方形序列组合来确保找到所有可能的方形序列.

public static void sqrSubseqCount(String in)
{
    List<List<Integer>> len_2_seq = listDoubleSequences(in);
    List<List<Integer>> prev_round = new ArrayList<>(len_2_seq);
    final Set<List<Integer>> next_round = new HashSet<>();

    int count = len_2_seq.size();

    System.out.println();
    System.out.println("Searching longer sequences:");

    while(!prev_round.isEmpty())
    {
        next_round.clear();

        prev_round.forEach(l -> len_2_seq.forEach(l2 -> {
            List<Integer> merge = merge(l , l2);

            if(merge != null && !next_round.contains(merge))
            {
                next_round.add(merge);
                printSeq(in , merge);
            }
        }));

        count += next_round.size();

        prev_round.clear();
        prev_round.addAll(next_round);
    }

    System.out.println();

    System.out.println("Total sequences found: " + count + " in: " + in);
}

注意事项:这是我用来打印序列的方法。

private static void printSeq(String in , List<Integer> seq)
{
    String seqStr = "";

    //convert the sequence of indices into the string represented
    //by seq
    for(int i : seq)
        seqStr += in.charAt(i);

    System.out.println(seq + " => " + seqStr);
}

大部分代码都可以通过多种方式进行优化，但我尽量使其尽可能简单。