Générer toutes les sous-chaînes uniques pour une chaîne donnée

Question

Étant donné une chaîne s , quelle est la méthode la plus rapide pour générer un ensemble de toutes ses sous-chaînes uniques?

Exemple: pour str = "aba" nous obtiendrions substrs={"a", "b", "ab", "ba", "aba"} .

L'algorithme naïf serait de parcourir la chaîne entière générant des sous-chaînes de longueur 1..n à chaque itération, donnant une limite supérieure de O(n^2) .

Une meilleure limite est-elle possible?

(il s'agit techniquement de devoirs, donc seuls les pointeurs sont les bienvenus)

Answer 1

Comme d'autres affiches l'ont dit, il existe potentiellement O (n ^ 2) sous-chaînes pour une chaîne donnée, donc leur impression ne peut pas se faire plus rapidement que cela. Cependant il existe une représentation efficace de l'ensemble qui peut être construit en temps linéaire: l'arbre des suffixes .

Answer 2

Il n'y a aucun moyen de le faire plus rapidement que O (n ² ) car il y a un total de O (n ² ) sous-chaînes dans une chaîne, donc si vous devez toutes les générer, leur nombre sera n(n + 1) / 2 dans le pire des cas, d'où la borne supérieure inférieure de O (n ² ) Ω (n ² ).

Answer 3

  First one is brute force which has complexity O(N^3) which could be brought down to    O(N^2 log(N))
 Second One using HashSet which has Complexity O(N^2)
 Third One using LCP by initially finding all the suffix of a given string which has the worst case O(N^2) and best case O(N Log(N)).



  First Soln:-

 import java.util.Scanner;
 public class DistinctSubString{
public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    System.out.print("Enter The string");
    String s=in.nextLine();
    long startTime = System.currentTimeMillis();
    int L=s.length();
    int N=L*(L+1)/2;
    String[] Comb=new String[N];
    for(int i=0,p=0;i<L;++i)
    {
        for(int j=0;j<(L-i);++j)
        {
            Comb[p++]=s.substring(j,i+j+1);
        }
    }
    /*for(int j=0;j<N;++j)
    {
        System.out.println(Comb[j]);
    }*/
    boolean[] val=new boolean[N];
    for(int i=0;i<N;++i)
        val[i]=true;
    int counter=N;
    int p=0,start=0;
    for(int i=0,j;i<L;++i)
    {
        p=L-i;
        for(j=start;j<(start+p);++j)
        {
            if(val[j])
            {
                //System.out.println(Comb[j]);
                for(int k=j+1;k<start+p;++k)
                {
                    if(Comb[j].equals(Comb[k]))
                    {
                        counter--;
                        val[k]=false;
                    }
                }
            }

        }

        start=j;
    }
    System.out.println("Substrings are "+N+" of which unique substrings are "+counter);
    long endTime = System.currentTimeMillis();
      System.out.println("It took " + (endTime - startTime) + " milliseconds");
}
  }
*********************************************************************************
   Second Soln:-

 import java.util.*;
 public class DistictSubstrings_usingHashTable {

 public static void main(String args[]) {
  // create a hash set

   Scanner in=new Scanner(System.in);
    System.out.print("Enter The string");
    String s=in.nextLine();
    int L=s.length();
    long startTime = System.currentTimeMillis();
  Set<String> hs = new HashSet<String>();
  // add elements to the hash set
  for(int i=0;i<L;++i)
    {
        for(int j=0;j<(L-i);++j)
        {
            hs.add(s.substring(j,i+j+1));
        }
    }
  System.out.println(hs.size());
  long endTime = System.currentTimeMillis();
  System.out.println("It took " + (endTime - startTime) + " milliseconds");
  }
  }
 

   Third Soln:-

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;


  public class LCPsolnFroDistinctSubString {


public static void main(String[] args) throws IOException{

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter Desired String ");
    String string=br.readLine();
    int length=string.length();
    String[] arrayString=new String[length];
    for(int i=0;i<length;++i)
    {
        arrayString[i]=string.substring(length-1-i,length);
    }

    Arrays.sort(arrayString);
    for(int i=0;i<length;++i)
    System.out.println(arrayString[i]);

    long num_substring=arrayString[0].length();

    for(int i=0;i<length-1;++i)
    {
        int j=0;
        for(;j<arrayString[i].length();++j)
        {
            if(!((arrayString[i].substring(0,j+1)).equals((arrayString)[i+1].substring(0,j+1))))
            {
                break;
            }
        }
        num_substring+=arrayString[i+1].length()-j;
    }
    System.out.println("unique substrings = "+num_substring);
}

  }
 

Answer 4

Pour les grandes oh ... Meilleur que vous pourriez faire serait de O(n^2)

Pas besoin de réinventer la roue, il n'est pas basé sur une des chaînes, mais sur un fixe, de sorte que vous aurez à prendre les concepts et de les appliquer à votre propre situation.

Les algorithmes de

Vraiment un Bon Livre Blanc à partir de MS

Dans la profondeur de PowerPoint

Le Blog de la chaîne de perms

Answer 5

eh bien, puisqu'il y a potentiellement n*(n+1)/2 sous-chaînes différentes (+1 pour la sous-chaîne vide), je doute que vous puissiez être meilleur que O(n*2) (pire cas). le plus simple est de les générer et d'utiliser une belle table de recherche O(1) (comme une table de hachage) pour exclure les doublons dès que vous les trouvez.