Квадратные подпоследовательности

Question

Вопрос. Строка называется квадратной строкой, если ее можно получить, объединив две копии одной и той же строки. Например, «abab», «aa» являются квадратными строками, а «aaa», «abba» - нет. Если задана строка, сколько подпоследовательностей строки являются квадратными строками? Подпоследовательность строки может быть получена путем удаления из нее нулей или более символов и сохранения относительного порядка остальных символов.

Входной формат

Первая строка содержит число тестовых примеров, Т. Т тестовые примеры следуют. Каждый случай содержит строку, S.

Формат вывода

Т выходных линий, по одному для каждого теста, содержащие требуемый ответ по модулю 1000000007.

Ограничения: 1≤T≤20 S будет имеют не более 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

Основная идея: мы можем организовать все squaresequences, которые могут быть получены из данной inputstring в виде дерева графа - в основном несколько деревьев слились с одним и несколькими родителями. Каждое из этих деревьев имеет одну из (локально) самых длинных возможных squaresequences как root, а листья - все квадраты последовательностей с длиной 2, которые могут быть получены из корневой последовательности. Теперь самым простым способом найти все возможные подпоследовательности было бы просто пройти это дерево любым способом и подсчитать узлы. Так как довольно сложно найти (локально) самые длинные возможные squaresequences для заданного ввода, мы используем другой вариант: начинаем с листьев и переходим к самым длинным последовательностям. Их можно легко найти, просто поиск всех возможных squaresequences с длиной 2.

Пример для отношений между squaresequences бы это:

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

Теперь, когда эти последовательности будут найдены, остальные довольно вперед: squaresubsequence с длиной n могут быть получены путем объединения двух последовательностей a и b с length_of_a + length_of_b = n в одной последовательности. Так как все squaresequences могут быть получены путем слияния последовательностей с 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 состоит из ряда squaresequences с length == 2, мы можем обеспечить, чтобы найти все возможные squaresequences просто найти все возможные комбинации squaresequences с 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); 
} 

Большая часть кода может быть оптимизирована множеством способов, но я старался максимально упростить ее.