Wyjaśnienie

Dwa ciągi można potasować, przerywając ich litery, aby utworzyć nowy ciąg, podobnie jak dwa stosy kart można potasować, tworząc pojedynczy stos.

Na przykład ciągi HELLOi WORLDmogą być tasowane, aby utworzyć HWEOLRLLOD, lub HEWORLLLDO, może po prostu HELLOWORLD.

To nie jest tasowanie, jeśli pierwotna kolejność liter nie zostanie zachowana. Na przykład, Dw WORLDnigdy nie może pojawić się, zanim Rpo tasuje. Oznacza to, że EHLLOWRDLOna przykład nie jest tasowaniem HELLOi WORLD, mimo że zawiera wszystkie oryginalne litery.

Sznurek jest przetasowaniem bliźniaków, jeśli można go uformować przez tasowanie dwóch identycznych strun. Na przykład ABACBDECDEjest tasowaniem bliźniaków, ponieważ można go utworzyć przez tasowanie ABCDEi ABCDE. DBEACBCADEnie jest tasiemkiem bliźniaków, ponieważ nie można go utworzyć przez tasowanie dwóch identycznych strun.

Szczegóły programu

Biorąc pod uwagę ciąg wejściowy, wypisuje, 0jeśli nie jest to losowy los bliźniaków, i wyprowadza jeden z bliźniaczych ciągów, jeśli jest to losowy los bliźniaków.

Możesz założyć, że łańcuch wejściowy ma długość od czterech do dwudziestu znaków i składa się wyłącznie z wielkich liter alfabetu. Powinien być w stanie działać w rozsądnym czasie, powiedzmy, poniżej 10 minut.

To jest golf golfowy, więc wygrywa najkrótsze rozwiązanie.

Przykład I / O

> ABACBDECDE
ABCDE

> DBEACBCADE
0

> FFFFFF
FFF

> FFGGG
0

> ABBA
0

> AABB
AB

> AABAAB
AAB

Mam przykładową (nie golfową) implementację .

Haskell, 114

main=getLine>>=putStrLn.f.p;f x=head$[a|(a,b)<-x,a==b]++["0"]
p[]=[([],[])];p(x:y)=do(a,b)<-p y;[(x:a,b),(a,x:b)]

Nie golfowany:

main :: IO ()
main = getLine >>= putStrLn . findMatch . partitions

-- | Find the first partition where the two subsequences are
-- equal. If none are, return "0".
findMatch :: [(String, String)] -> String
findMatch ps = head $ [a | (a,b) <- ps, a == b] ++ ["0"]

-- | Return all possible partitions of the input into two
-- subsequences. Preserves the order of each subsequence.
--
-- Example:
-- partitions "AB" == [("AB",""),("B","A"),("A","B"),("","AB")]
partitions :: [a] -> [([a], [a])]
partitions []     = [([], [])]
partitions (x:xs) = do (a, b) <- partitions xs
                       [(x:a, b), (a, x:b)]

Wyjaśnienie:

Większość pracy jest wykonywana w partitionsfunkcji. Działa poprzez rekurencyjne generowanie wszystkich partycji (a, b)ogona listy, a następnie za pomocą monady listy, aby dołączyć element początkowy xdo każdej z nich i zebrać wszystkie wyniki.

findMatchdziała poprzez filtrowanie tej listy, aby pozostały tylko partycje, w których podsekwencje są równe. Następnie zwraca pierwszą podsekwencję w pierwszej partycji. Jeśli nie pozostanie, lista jest pusta, więc "0"zamiast tego zwracana jest dołączona na końcu.

main po prostu odczytuje dane wejściowe, przekazuje je przez te dwie funkcje i drukuje.

R, 113 znaków

l=length(x<-charToRaw(scan(,'')));max(apply(combn(l,l/2),2,function(i)if(all(x[i]==x[-i]))rawToChar(x[i])else 0))

Ungolfed (i zamiast tego funkcja, która pobiera ciąg):

untwin <- function(x) {
  x <- charToRaw(x)
  indMtx <- combn(length(x),length(x)/2)
  res <- apply(indMtx, 2, function(i) {
    if (all(x[i]==x[-i]))
      rawToChar(x[i])
    else
      0
  })
  max(res)
}

untwin("ABACBDECDE") # "ABCDE"
untwin("DBEACBCADE") # 0

Rozwiązanie opiera się na combnfunkcji, która generuje wszystkie kombinacje indeksów jako kolumny w macierzy. applynastępnie stosuje funkcję do każdej kolumny (wymiaru 2) w macierzy i zwraca wektor ciągów lub zer. maxnastępnie znajdź największy ciąg (który przebija 0).

Fajną cechą w R jest możliwość wybrania podzbioru wektora podanego wektorem indeksów, a następnie wybrania dopełnienia tego podzbioru przez zanegowanie indeksów:x[i] == x[-i]

Mathematica, 87

Jest to bezpośrednio oparte na poście Hammara, ale mam nadzieję, że jest wystarczająco wyraźne, aby zasługiwać na opublikowanie.

<<Combinatorica`

f=Catch[Cases[Characters@#~KSetPartitions~2,{x_,x_}:>Throw[""<>x]];0]&

Test:

f /@ {"ABACBDECDE", "DBEACBCADE", "FFFFFF", "FGG", "ABBA", "AABB", "AABAAB"}

{„ABCDE”, 0, „FFF”, 0, 0, „AB”, „AAB”}

re

string c(string in,string a=[],string b=[]){
    if(in.length==0)return a==b?a;"0";
    auto r=c(in[1..$],a~in[0],b);
    return r=="0"?c(in[1..$],a,b~in[0]):r;
}
void main(){writeln(c(readline));}

używając głębokości pierwszego wyszukiwania rekurencyjnego

Mogę przyspieszyć dzięki int i = min(a.length,b.length);if(a[0..i]!=b[0..i])return "0";klauzuli ochronnej

Ruby, 89 znaków

s=->a,x,y{a=="\n"?x==y ?x:?0:[s[b=a[1..-1],x+c=a[0],y],s[b,x,y+c]].max}
$><<s[gets,'','']

Ten kod implementuje prosty algorytm wyszukiwania rekurencyjnego. Dane wejściowe należy podać na STDIN.

Perl, 68 znaków

/^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0

Zakłada się, że łańcuch wejściowy znajduje się w $_zmiennej, a wynikiem jest wartość wyrażenia. Końcowe znaki nowej linii w danych wejściowych są ignorowane. Możesz uruchomić to z wiersza poleceń w następujący sposób:

perl -lne 'print /^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0'

Ten kod wykorzystuje silnik wyrażeń regularnych Perla (a zwłaszcza jego funkcję wykonywania kodu osadzonego ) w celu wykonania śledzenia wstecznego. Zasadniczo dopasowuje ciąg wejściowy do ^((.+))+$wyrażenia regularnego, śledząc nieparzyste i parzyste podelementy w $xi $,, i odrzuca dopasowanie na końcu, jeśli dwa nie są równe.

Python, 168 znaków

def f(s):
 c=s[0]
 d=i=r=0
 if s==c+c:r=c
 while i+1 and i<=len(s)/2 and not r:
  if i:d=f(s[1:i]+s[i+1:])
  if d:r=c+d
  i=s.find(c,i+1)
 return r
print f(raw_input())