Square Subsequence

Question

Ciąg jest nazywany kwadratowym ciągiem znaków, jeśli można go uzyskać, łącząc dwie kopie tego samego ciągu znaków. Na przykład "abab", "aa" są kwadratowymi łańcuchami, a "aaa", "abba" nie są. Biorąc pod uwagę łańcuch, ile podciągów ciągu jest ciągami kwadratowymi? Podsekwencję ciągu znaków można uzyskać, usuwając z niego zero lub więcej znaków i zachowując względną kolejność pozostałych znaków. Podsekwencja nie musi być unikalna.

np string 'aaa' będzie miała 3 podsekwencje kwadratowych

Answer 1

Uwaga 1: Długość ciągu kwadratowego jest zawsze równa.

Obserwacja 2: Każdy kwadrat podciągiem długości 2n (n> 1) jest połączeniem dwóch krótszych subsekwencji: jeden o długości 2 (n-1) i jeden o długości 2

pierwsze znaleźć podsekwencje o długości dwóch, tj. znaki, które występują dwa lub więcej razy w ciągu znaków. Nazwiemy te par. Dla każdego podciągu o długości 2 (1 para) zapamiętaj pozycję pierwszego i ostatniego znaku w sekwencji.

Załóżmy teraz, że mamy wszystkie podsekwencje długości 2 (n-1) i wiemy dla każdego, gdzie w ciągu pierwsza i druga część zaczyna się i kończy. Możemy znaleźć sekwencje o długości 2n za pomocą obserwacji 2:

Przejrzyj wszystkie podciągi długości 2 (n-1) i znajdź wszystkie pary, w których pierwszy element w parze znajduje się między ostatnią pozycją pierwszej części i pierwsza pozycja drugiej części, a druga pozycja leży po ostatniej pozycji drugiej części. Za każdym razem, gdy taka para zostanie znaleziona, połącz ją z obecnym podsekwencją długości 2 (n-2) w nowy podciąg długości 2n.

Powtórz ostatni krok, dopóki nie zostaną znalezione żadne nowe podcięcia kwadratów.

Answer 2

Psuedocode:

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

Oto rozwiązanie przy użyciu 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); 

I tu jest moja metoda rozszerzenie PowerSet, wraz z metoda wybierania "Wybierz" wymagana przez 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

początkowo czerpią wszystkich możliwych sub-sekwencje, a potem sprawdzi, czy pochodzi sub-sekwencja jest kwadratem sub-sekwencji lub nie

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