Explication

Deux chaînes peuvent être mélangées en intercalant leurs lettres pour former une nouvelle chaîne, tout comme deux piles de cartes peuvent être mélangées pour former une seule pile.

Par exemple, les chaînes HELLOet WORLDpeuvent être mélangées pour former HWEOLRLLOD, ou HEWORLLLDO, ou peut-être simplement HELLOWORLD.

Ce n'est pas un mélange si l'ordre des lettres d'origine n'est pas conservé. Par exemple, le Din WORLDne peut jamais apparaître avant le Raprès avoir été mélangé. Cela signifie que EHLLOWRDLO, par exemple, n'est pas un mélange de HELLOet WORLD, même s'il contient toutes les lettres originales.

Une chaîne est un mélange de jumeaux si elle peut être formée en mélangeant deux chaînes identiques. Par exemple, ABACBDECDEest un mélange de jumeaux car il peut être formé par mélange ABCDEet ABCDE. DBEACBCADEn'est pas un mélange de jumeaux car il ne peut pas être formé en mélangeant deux chaînes identiques.

Détails du programme

Étant donné une chaîne d'entrée, sortez 0si ce n'est pas un mélange de jumeaux, et sortez l'une des chaînes jumelles s'il s'agit d'un mélange de jumeaux.

Vous pouvez supposer que la chaîne d'entrée a une longueur comprise entre quatre et vingt caractères et est entièrement composée de caractères alphabétiques majuscules. Il devrait pouvoir fonctionner dans un laps de temps raisonnable, disons moins de 10 minutes.

C'est le golf de code, donc la solution la plus courte l'emporte.

Exemple d'E / S

> ABACBDECDE
ABCDE

> DBEACBCADE
0

> FFFFFF
FFF

> FFGGG
0

> ABBA
0

> AABB
AB

> AABAAB
AAB

J'ai un exemple d'implémentation (non-golfé) .

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)]

Non golfé:

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)]

Explication:

La plupart du travail se fait dans la partitionsfonction. Il fonctionne en générant récursivement toutes les partitions (a, b)de la fin de la liste, puis en utilisant la monade de liste pour ajouter l'élément initial xà chacune d'entre elles et rassembler tous les résultats.

findMatchfonctionne en filtrant cette liste afin qu'il ne reste que les partitions où les sous-séquences sont égales. Il renvoie ensuite la première sous-séquence de la première partition. S'il n'en reste pas, la liste est vide, donc le "0"texte ajouté à la fin est renvoyé à la place.

main lit simplement l'entrée, la fait passer par ces deux fonctions et l'imprime.

R, 113 caractères

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))

Non golfé (et à la place une fonction qui prend la chaîne):

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

La solution repose sur la combnfonction qui génère toutes les combinaisons d'indices sous forme de colonnes dans une matrice. applyapplique ensuite une fonction à chaque colonne (dimension 2) de la matrice et renvoie un vecteur de chaînes ou de zéros. maxpuis trouvez la plus grande chaîne (qui l'emporte sur 0).

Une caractéristique intéressante de R est la possibilité de sélectionner un sous-ensemble d'un vecteur donné un vecteur d'indices, puis de sélectionner le complément de ce sous-ensemble en annulant les indices:x[i] == x[-i]

Mathematica, 87

Ceci est directement basé sur le post de hammar, mais j'espère qu'il est suffisamment distinct pour mériter d'être publié.

<<Combinatorica`

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

Tester:

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

{"ABCDE", 0, "FFF", 0, 0, "AB", "AAB"}

ré

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

utilisation de la première recherche récursive en profondeur

Je peux faire plus vite avec une int i = min(a.length,b.length);if(a[0..i]!=b[0..i])return "0";clause de garde

Ruby, 89 caractères

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,'','']

Ce code implémente un algorithme de recherche récursif simple. L'entrée doit être donnée sur STDIN.

Perl, 68 caractères

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

La chaîne d'entrée supposée être dans la $_variable, la sortie est la valeur de l'expression. Les retours à la ligne en fin d'entrée sont ignorés. Vous pouvez l'exécuter à partir de la ligne de commande comme ceci:

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

Ce code utilise le moteur d'expression rationnelle de Perl (et en particulier sa fonction d' exécution de code intégrée) pour effectuer le retour arrière. Fondamentalement, il fait correspondre la chaîne d'entrée à l'expression rationnelle ^((.+))+$, en gardant une trace des sous-correspondances impaires et paires dans $xet $,, et en rejetant la correspondance à la fin si les deux ne sont pas égaux.

Python, 168 caractères

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())