स्क्वायर उपक्रम

Question

एक स्ट्रिंग को स्क्वायर स्ट्रिंग कहा जाता है यदि इसे उसी स्ट्रिंग की दो प्रतियों को संयोजित करके प्राप्त किया जा सकता है। उदाहरण के लिए, "अबाब", "एए" स्क्वायर स्ट्रिंग्स हैं, जबकि "aaa", "abba" नहीं हैं। एक स्ट्रिंग को देखते हुए, स्ट्रिंग के कितने बाद स्क्वायर स्ट्रिंग हैं? एक स्ट्रिंग के बाद शून्य या उससे अधिक वर्णों को हटाकर और शेष वर्णों के सापेक्ष क्रम को बनाए रखकर प्राप्त किया जा सकता है। बाद में अद्वितीय होने की आवश्यकता नहीं है।

जैसे स्ट्रिंग 'एएए' 3 वर्ग subsequences

होगा

Answer 1

निरीक्षण 1: स्क्वायर स्ट्रिंग की लंबाई हमेशा भी होती है।

अवलोकन 2: लंबाई 2n का हर वर्ग किसी परिणाम (एन> 1) दो छोटे subsequences का एक संयोजन है: लंबाई 2 (एन -1) और लंबाई में से एक 2.

पहले, subsequences को खोजने में से एक लंबाई दो, यानी वर्ण जो दो बार या अधिक स्ट्रिंग में होते हैं। हम इन जोड़े पर कॉल करेंगे। लंबाई 2 (1 जोड़ी) के प्रत्येक अनुवर्ती के लिए, अनुक्रम में पहले और अंतिम चरित्र की स्थिति याद रखें।

अब, मान लीजिए कि हमारे पास लंबाई 2 (एन -1) के सभी बाद हैं, और हम स्ट्रिंग में प्रत्येक और दूसरे भाग के लिए शुरू होते हैं और समाप्त होते हैं। हम अवलोकन 2:

लंबाई 2 (एन -1) के सभी बाद के माध्यम से जाएं, और सभी जोड़ों को ढूंढें जहां जोड़ी में पहला आइटम पहले भाग की अंतिम स्थिति के बीच है और दूसरे भाग की पहली स्थिति, और दूसरा आइटम दूसरे भाग की अंतिम स्थिति के बाद है। हर बार ऐसी जोड़ी पाई जाती है, लंबाई 2 (एन -2) के वर्तमान अनुक्रम के साथ लंबाई 2 एन के नए अनुक्रम में गठबंधन करें।

अंतिम चरण दोहराएं जब तक कि कोई और नया वर्ग अनुवर्ती न मिले।

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

यहाँ एक समाधान 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 द्वारा आवश्यक "चुनें" एक्सटेंशन विधि:

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