trouver tous distincts sous-chaîne d'une chaîne de caractères

bonjour les gars, j'ai été donné de devoirs problème où il me demande de trouver tous distincts sous-chaîne d'une chaîne de caractères.
J'ai mis en œuvre une méthode qui vous permettra de connaître toutes les sous-chaînes d'une chaîne, mais j'ai besoin d'une aide pour comprendre comment comptez pas l'un qui est déjà compté une fois que substring car la mission est de trouver bien distinctes.

public int printSubstrings1(int length)
{ 
    for(int i=0; i<text.length()-length+1;i++)
    {
        String sub = text.substring(i,length+i);

        counter++;
    }
    return counter;

}

ici, je suis de passage la longueur des chaînes que j'ai envie de te chaîne de caractères donnée.
je suis faire que par le biais d'une autre méthode.

donc exemple de chaîne de caractères donnée est "fred" que les différents sous-chaînes est de 10. ma méthode de sortie droit de réponse étant donné que la chaîne ne contient pas répété lettres. je suis bloqué sur la partie où je ne se répète sous-chaînes.

si j'ai d'entrée de fred. c'est ce que ma méthode de sortie

longueur 1

f

r

e

d

longueur 2

fr

re

ed

longueur 3

fre

rouge

longueur 4

fred

Les mettre dans un Set - "Un Ensemble est une collection qui ne contient pas les éléments en double"
bonne idée merci à vous dire de la matrice de droite. que comment puis-je vérifier si la chaîne de caractères déjà exister en elle. depuis le tableau n'a pas . contient de la méthode en elle de la classe.
stackoverflow.com/questions/5076099/...
pouvez-vous donner des exemples de l'Ensemble.
java.util.HashSet, par exemple.

InformationsquelleAutor Dfsdfsdf Dsfsdfdsf | 2012-11-03

public ArrayList<String> getAllUniqueSubset(String str) {
        ArrayList<String> set = new ArrayList<String>();
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length() - i; j++) {
                String elem = str.substring(j, j + (i+1));
                if (!set.contains(elem)) {
                    set.add(elem);
                }
            }
        }
        return set;
    }

Votre réponse serait beaucoup plus utile si vous voulez ajouter quelques remarques

InformationsquelleAutor Shubham Chauhan

Ici l'exemple avec un Ensemble

public int printSubstrings1(int length) {
    Set<String> set = new HashSet<String>();
    for(int i=0; i < text.length() - length + 1; i++) {
        String sub = text.substring(i,length+i);
        set.add(sub);
    }
    for (String str : set) {
        System.out.println(str);
    }
    return set.size();
}

InformationsquelleAutor jlordo

0

Insérez les nouveaux sous-chaîne dans un tableau et vérifier si elle est déjà disponible, il n'est pas de l'ajouter à la matrice d'autre de le faire. Quand faire la boucle dans le tableau et d'imprimer les différents sous chaînes de caractères.

Pour vérifier si un élément existe dans un tableau de créer une fonction qui prend un tableau et une valeur en tant que paramètres. Il serait de parcourir le tableau à la recherche de la valeur si trouvé return true. En dehors de la boucle de retour faux.

par exemple
```
public static boolean(String target, String[] arr)
{
  for(int i = 0; i < arr.length; i++){
      if(arr[i].equals(target))
         return true;
  }
   return false;
}
```
- Si votre tableau est initialisé les cellules, ce qui permettra de jeter un NullPointerException
InformationsquelleAutor Ayman Farhat
0

Cet algorithme utilise juste le Z-fonction /Z algorithme.

Pour chaque préfixe i de la parole, l'inverser et faire z_function sur elle.
Le nombre de nouveaux distinct sous-chaînes qui se terminent dans i est (the length of the prefix) — (maximum value in the z_function array).
Le pseudo-code ressemble à ceci:
```
string s; cin >> s;
int sol = 0
foreach i to s.size()-1
    string x = s.substr( 0 , i+1 );
    reverse( x.begin() , x.end() );
    vector<int> z = z_function( x );
    //this works too
    //vector<int> z = prefix_functionx(x); 
    int mx = 0;
    foreach j to x.size()-1
        mx = max( mx , z[j] );
    sol += (i+1) - mx; 

cout << sol;
```
Le temps de la complexité de cet algorithme est O(n^2). Le maximum peut être retourné à partir de la z_function ainsi.

Source.

Ce n'est pas ma réponse originale à cette question. Je suis simplement un lien et le coller dans le cas où le lien va vers le bas.

InformationsquelleAutor user5735122
0

J'ai suivi ce lien.Prend acte du contenu à partir d'une même réponse dans quora

La solution consiste à construire le suffixe tableau et ensuite trouver le nombre de sous-chaînes distinctes basées sur la plus Longue de la Commune de Préfixes.

Une observation clé ici est que:

Si vous regardez à travers les préfixes de chaque suffixe d'une chaîne de caractères, que vous avez couvert toutes les sous-chaînes d'une chaîne.

Prenons un exemple: la BANANE

Suffixes sont: 0) BANANE 1) ANANA 2) NANA 3) ANA 4) NA 5) UN

Il serait beaucoup plus facile de passer par les préfixes si l'on répartit l'ensemble ci-dessus de suffixes, comme on peut le sauter à la répétition des préfixes facilement.

Triés ensemble de suffixes: 5) 3) ANA 1) ANANA 0) BANANE 4) NA 2) NANA

À partir de maintenant,

LCP = le plus long Préfixe Commun de 2 cordes.

Initialiser

ans = longueur(premier suffixe) = longueur("A") = 1.

Considérons maintenant les paires consécutives de suffixes, j'.e, [A, ANA], [ANA, ANANA], [ANANA, de la BANANE], etc. à partir de la consigne de tri des suffixes.

Nous pouvons voir que, LCP("UN", "ANA") = "UN".

Tous les caractères qui ne font pas partie du préfixe commun de contribuer à une nette sous-chaîne. Dans le cas ci-dessus, ils sont 'N' et 'Un'. Donc, ils doivent être ajoutés à ans.

Nous avons donc, 1 2 ans += longueur("ANA") - LCP("UN", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Faire de même pour la prochaine paire de jours suffixes: ["ANA", "ANANA"]

1 2 3 4 LCP("ANA", "ANANA") = "ANA". ans += longueur("ANANA") - longueur(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5.

De même, nous avons:

1 2 LCP("ANANA", "BANANE") = 0 ans = ans + longueur("BANANE") - 0 = 11

1 2 LCP("la BANANE", "NA") = 0 ans = ans + longueur("NA") - 0 = 13

1 2 LCP("NA", "NANA") = 2 ans = ans + longueur("NANA") - 2 = 15

Par conséquent, le nombre de sous-chaînes distinctes pour la chaîne "BANANE" = 15.

InformationsquelleAutor Rajesh M

Vous devez vous connecter pour publier un commentaire.