Поиск подстроки строки, содержащей все слова в массиве

Question

У меня есть строка и массив слов, и я должен написать код, чтобы найти все подстроки строки, содержащие все слова в массиве в любом порядке. Строка не содержит специальных символов/цифр, и каждое слово разделяется пробелом.

Например:

Строка Дано:

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

Слова в массиве:

aaaa 
bbbb 
cccc 

Примеры выхода:

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 

Я реализовал это с использованием циклов, но это очень неэффективно.

Как я могу сделать это более эффективно?

Мой код:

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

Мой первый подход будет что-то вроде следующего псевдокода

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 
    } 

Это должно иметь достойную производительность, так как вы только пересечь строку один раз.

[EDIT]

Это реализация моего псевдо-кода, попробовать его и посмотреть, если он работает лучше или хуже. Он работает в предположении, что соответствующая подстрока будет найдена, как только вы найдете последнее слово. Если вы действительно хотите всех матчей, изменить линии отмечены //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

Вот другой подход:

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

Это выведет:

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

Я знаю, что результат не полный: у вас есть только доступные комбинации, полностью выдвинуто, но вы получили все из них.