Biorąc pod uwagę ciąg liter i zestaw słów, wypisz kolejność słów, aby można je było znaleźć w ciągu, upuszczając niepotrzebne litery. Słowa mogą występować więcej niż jeden raz w zestawie słów. Łańcuch wejściowy i wszystkie słowa składają się z 1 do 1000 małych liter. Litery, które mają być upuszczone, mogą występować wewnątrz słów lub między słowami.

Twój program lub funkcja może zaakceptować ciąg liter i słowa jako listy, ciąg znaków lub ze STDIN i musi wypisać wszystkie słowa w prawidłowej kolejności jako wyjście listy lub ciągu. Jeśli istnieje więcej niż jedno prawidłowe rozwiązanie, wypisz tylko jedno z nich. Jeśli nie ma możliwego poprawnego rozwiązania, wypisz pustą listę lub pusty ciąg.

Przykłady:

dogcatfrog cat frog dog
-> dog cat frog

xxcatfixsxhingonxgrapexxxfishingcxat cat grape catfish fishing
-> catfish grape fishing cat

dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
-> da ab ba ba ba cc bb aa ac dc db dd

flea antelope
->
(no solution)

To jest kod golfowy. Najniższa liczba bajtów wygrywa.

Edycja: wyjaśniono, że dodatkowe znaki mogą znajdować się w słowach.

Pyth, 20 24 bajtów

Moja pierwsza próba na Pyth :)

Jcw;FG.ptJI:hJj".*"G0jdG

Jak to działa:

Jcw;FG.ptJI:hJj".*"G0jdG
Jcw                         assign("J",chop(input()))
    FG.ptJ                  for G in permutations(tail(J)):
          I:hJj".*"G0        if match(head(J),join(".*",G)):
                     jdG      print(join(" ",G))

Uwagi: w trzecim przykładzie ( dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc) zajmuje dużo czasu .

Pyth, 10 bajtów

h@s./Myz.p

Demonstracja

Ten program ma bardzo brutalną siłę. Najpierw konstruuje każdy podzbiór danych wejściowych, a następnie każdą partycję podzbiorów, a następnie sprawdza, czy jest to pierwszy, który stanowi zmianę kolejności listy słów. Żadne możliwości nie są obsługiwane przez błędy bez wyjścia na standardowe wyjście, na co pozwala meta konsensus. Błąd można usunąć dla 2 dodatkowych bajtów.

Pamiętaj, że w przypadku wielu podanych przypadków testowych program nie zostanie ukończony w rozsądnym czasie.

JavaScript (ES6), 119 bajtów

(s,a,t=``,...r)=>a[0]?a.find((w,i)=>(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)))&&q:~s.search(t.split``.join`.*`)&&(q=r)

Akceptuje ciąg znaków i tablicę słów i zwraca tablicę słów lub undefinedw przypadku awarii. Dodaj 2 bajty, jeśli musi zwrócić pusty ciąg w przypadku niepowodzenia ( ?q:``), w którym to przypadku ta alternatywna wersja ma tylko 120 bajtów i zwraca pusty ciąg w przypadku awarii, a nawet może zapisać 2 bajty, jeśli może zwrócić 0 w przypadku awarii:

(s,a,t=``,...r)=>a[0]?a.reduce((q,w,i)=>q||(b=[...a],b.splice(i,1),f(s,b,w+t,w,...r)),0):~s.search([...t].join`.*`)?r:``

(Po napisaniu tego zauważyłem, że algorytm jest w zasadzie taki sam jak odpowiedź Pyth @ KennyLau.)

Edytowana edycja: zaktualizowana po wyjaśnieniu pytania, ale teraz jest bardzo powolna w trzecim przypadku testowym; Wyłączyłem go poprzedniej nocy i dziś rano zauważyłem, że znalazło rozwiązanie, gdzieś pomiędzy 30 a 40 godzin później. Byłem naprawdę podły i podałem mu rozwiązanie (najlepiej działa z rozwiązaniem odwróconym, które natychmiast zweryfikuje).

Java 7, 256 bajtów

import java.util.*;String c(String...a){Map s=new HashMap();int j,i=1,l=a[0].length();for(;i<a.length;i++)if((j=a[0].indexOf(a[i]))>-1)s.put(j,s.get(j)!=null?s.get(j)+" "+a[i]:a[i]);a[0]="";for(j=0;j<l;j++)a[0]+=s.get(j)!=null?s.get(j)+" ":"";return a[0];}

Zdecydowanie powinna być możliwa gra w golfa przy użyciu innego podejścia, ale na razie to zrobi ...

Kod niepoznany i testowy:

Wypróbuj tutaj.

import java.util.*;
class M{
  static String c(String... a){
    Map s = new HashMap();
    int j,
        i = 1,
        l = a[0].length();
    for(; i < a.length; i++){
      if((j = a[0].indexOf(a[i])) > -1){
        s.put(j, s.get(j) != null
                  ? s.get(j) + " " + a[i]
                  : a[i]);
      }
    }
    a[0] = "";
    for(j = 0; j < l; j++){
      a[0] += s.get(j) != null
               ? s.get(j) + " "
               : "";
    }
    return a[0];
  }

  public static void main(String[] a){
    System.out.println(c("dogcatfrog", "cat", "frog", "dog"));
    System.out.println(c("xxcatfixsxhingonxgrapexxxfishingcxat", "cat", "grape", "catfish", "fishing"));
    System.out.println(
        c("dababbabadbaccbcbaaacdacdbdd ", "aa", "bb", "cc", "dd", "ba", "ba", "ba", "ab", "ac", "da", "db", "dc"));
    System.out.println(c("flea", "antelope"));
  }
}

Wynik:

dog cat frog 
cat grape fishing 
da ab ba ba ba bb db ac cc aa dd 

Groovy (44 bajty)

Nie mogę uwierzyć, że nikt inny nie użył do tego wyrażeń regularnych ...

{a,b->a.findAll(/${b.join('|')}/).join(" ")}

Wyjaśnienie

/${b.join('|')}/- Utwórz wyrażenie regularne, aby znaleźć dowolne słowo w ciągu.
.findAll(...)- Znajdź i zbierz wszystkie wystąpienia ciągu w tablicy.
.join(" ")- Połącz tablicę ze spacjami.

Zasadniczo, jeśli nie ma żadnych wystąpień, tablica jest pusta i niejawnie zwraca pusty ciąg. Jeśli znajdzie wystąpienia, zwraca obiekt tablicy z wystąpieniami, a następnie spłaszcza go w ciąg.