Recherche de sous-chaînes de chaînes contenant tous les mots du tableau

Question

J'ai une chaîne et un tableau de mots et je dois écrire du code pour trouver toutes les sous-chaînes de la chaîne qui contiennent tous les mots du tableau dans n'importe quel ordre. La chaîne ne contient aucun caractère/chiffre spécial et chaque mot est séparé par un espace.

Par exemple:

Chaîne suivant:

aaaa aaaa aaaa aaaa cccc bbbb bbbb bbbb bbbb aaaa bbbb cccc 

mots en réseau:

aaaa 
bbbb 
cccc 

exemples de sortie:

aaaa aaaa aaaa aaaa cccc bbbb bbbb bbbb bbbb  

aaaa aaaa aaaa aaaa cccc bbbb  

aaaa cccc bbbb bbbb bbbb bbbb  

cccc bbbb bbbb bbbb bbbb aaaa 

aaaa cccc bbbb 

J'ai implémenté ceci en utilisant des boucles, mais c'est très inefficace.

Comment puis-je le faire plus efficacement?

Mon code:

for(int i=0;i<str_arr.length;i++) 
    { 
     if((str_arr.length - i) >= words.length) 
     { 
      String res = check(i); 
      if(!res.equals("")) 
      { 
       System.out.println(res); 
       System.out.println(""); 
      } 
      reset_all(); 
     } 
     else 
     { 
      break; 
     } 
    } 

public static String check(int i) 
{ 
    String res = ""; 
    num_words = 0; 

    for(int j=i;j<str_arr.length;j++) 
    { 
     if(has_word(str_arr[j])) 
     { 
      t.put(str_arr[j].toLowerCase(), 1); 
      h.put(str_arr[j].toLowerCase(), 1); 

      res = res + str_arr[j]; //+ " "; 

      if(all_complete()) 
      { 
       return res; 
      } 

      res = res + " "; 
     } 
     else 
     { 
      res = res + str_arr[j] + " "; 
     } 

    } 
    res = ""; 
    return res; 
} 

Answer 1

Ma première approche serait quelque chose comme le pseudo-code

for word:string { 
    if word in array { 
     for each stored potential substring { 
     if word wasnt already found { 
      remove word from notAlreadyFoundList 
      if notAlreadyFoundList is empty { 
      use starting pos and ending pos to save our substring 
      } 
     } 
     store position and array-word as potential substring 
    } 

suivante Cela devrait avoir des performances décentes puisque vous ne traversez la chaîne une fois.

[EDIT]

C'est une implémentation de mon pseudo-code, essayer et voir si elle fonctionne mieux ou pire. Cela fonctionne sous l'hypothèse qu'une sous-chaîne correspondante est trouvée dès que vous trouvez le dernier mot. Si vraiment vous voulez tous matches, changer les lignes marquées //ALLMATCHES:

class SubStringFinder { 
    String textString = "aaaa aaaa aaaa aaaa cccc bbbb bbbb bbbb bbbb aaaa bbbb cccc"; 
    Set<String> words = new HashSet<String>(Arrays.asList("aaaa", "bbbb", "cccc")); 

    public static void main(String[] args) { 
     new SubStringFinder(); 
    } 

    public SubStringFinder() { 
     List<PotentialMatch> matches = new ArrayList<PotentialMatch>(); 
     for (String textPart : textString.split(" ")) { 
      if (words.contains(textPart)) { 
       for (Iterator<PotentialMatch> matchIterator = matches.iterator(); matchIterator.hasNext();) { 
        PotentialMatch match = matchIterator.next(); 
        String result = match.tryMatch(textPart); 
        if (result != null) { 
         System.out.println("Match found: \"" + result + "\""); 
         matchIterator.remove(); //ALLMATCHES - remove this line 
        } 
       } 
       Set<String> unfound = new HashSet<String>(words); 
       unfound.remove(textPart); 
       matches.add(new PotentialMatch(unfound, textPart)); 
      }// ALLMATCHES add these lines 
      // else { 
      // matches.add(new PotentialMatch(new HashSet<String>(words), textPart)); 
      // } 
     } 
    } 

    class PotentialMatch { 
     Set<String> unfoundWords; 
     StringBuilder stringPart; 
     public PotentialMatch(Set<String> unfoundWords, String part) { 
      this.unfoundWords = unfoundWords; 
      this.stringPart = new StringBuilder(part); 
     } 
     public String tryMatch(String part) { 
      this.stringPart.append(' ').append(part); 
      unfoundWords.remove(part);     
      if (unfoundWords.isEmpty()) { 
       return this.stringPart.toString(); 
      } 
      return null; 
     } 
    } 
} 

Answer 2

Voici une autre approche:

public static void main(String[] args) throws FileNotFoundException { 
    // init 
    List<String> result = new ArrayList<String>(); 
    String string = "aaaa aaaa aaaa aaaa cccc bbbb bbbb bbbb bbbb aaaa bbbb cccc"; 
    String[] words = { "aaaa", "bbbb", "cccc" }; 
    // find all combs as regexps (e.g. "(aaaa)+(bbbb)+(cccc)*cccc", "(aaaa)+(cccc)+(bbbb)*bbbb") 
    List<String> regexps = findCombs(Arrays.asList(words)); 
    // compile and add 
    for (String regexp : regexps) { 
     Pattern p = Pattern.compile(regexp); 
     Matcher m = p.matcher(string); 
     while (m.find()) { 
      result.add(m.group()); 
     } 
    } 
    System.out.println(result); 
} 

private static List<String> findCombs(List<String> words) { 
    if (words.size() == 1) { 
     words.set(0, "(" + Pattern.quote(words.get(0)) + ")*" + Pattern.quote(words.get(0))); 
     return words; 
    } 
    List<String> list = new ArrayList<String>(); 
    for (String word : words) { 
     List<String> tail = new LinkedList<String>(words); 
     tail.remove(word); 
     for (String s : findCombs(tail)) { 
      list.add("(" + Pattern.quote(word) + " ?)+" + s); 
     } 
    } 
    return list; 
} 

Affichera:

[aaaa bbbb cccc, aaaa aaaa aaaa aaaa cccc bbbb bbbb bbbb bbbb, cccc bbbb bbbb bbbb bbbb aaaa] 

Je sais que le résultat est pas complet: vous avez seulement les combinaisons disponibles, complètement étendu, mais vous les avez tous.