Ihre Aufgabe zur Lösung des SLCSC-Problems besteht darin, den kürzestmöglichen Code zur Lösung des Problems der längsten gemeinsamen Folge zu finden .

Eine gültige Lösung für das LCS-Problem für zwei oder mehr Zeichenfolgen S ₁ ,… S _n ist eine beliebige Zeichenfolge T mit maximaler Länge, so dass die Zeichen von T in allen S _i in derselben Reihenfolge wie in T erscheinen .

Beachten Sie, dass T nicht Teil sein muss Zeichenfolge von S _i .

Beispiel

Die Strings axbyczund xaybzchaben 8 gemeinsame Teilsequenzen der Länge 3:

abc abz ayc ayz xbc xbz xyc xyz

All dies wäre eine gültige Lösung für das LCS-Problem.

Einzelheiten

Schreiben Sie ein Programm oder eine Funktion, die das LCS-Problem löst, wie oben erläutert, und befolgen Sie dabei die folgenden Regeln:

• Die Eingabe besteht aus zwei oder mehr Zeichenfolgen, die nur Kleinbuchstaben enthalten.

  Sie können diese Zeichenfolgen als Array von Zeichenfolgen oder als einzelne Zeichenfolge mit einem Trennzeichen Ihrer Wahl lesen.

• Ihr Code muss eine einzelne der möglichen Lösungen für das Problem ausgeben, optional gefolgt von einem Zeilenvorschub oder umgeben von Anführungszeichen.

• Sie können davon ausgehen, dass die Zeichenfolgen kürzer als 1000 Zeichen sind und dass höchstens 20 Zeichenfolgen vorhanden sind.

  Innerhalb dieser Grenzen sollte Ihr Code theoretisch wie erwartet funktionieren (bei unbegrenzter Zeit und unbegrenztem Speicher).

• Ihr Code muss die kombinierten Testfälle des nächsten Abschnitts in weniger als einer Stunde auf meinem Computer (Intel Core i7-3770, 16 GiB RAM) abschließen.

  Ansätze, die einfach alle möglichen Teilsequenzen durchlaufen, halten das Zeitlimit nicht ein.

• Die Verwendung von integrierten Funktionen, die diese Aufgabe trivialisieren, z. B. LongestCommonSequence, ist nicht zulässig.

Es gelten die Standardregeln für Code-Golf .

Testfälle

a
ab

Ausgabe: a

aaaaxbbbb
bbbbxcccc
ccccxaaaa

Ausgabe: x

hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

Ausgabe: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrloder eine andere gemeinsame Teilsequenz gleicher Länge

riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

Ausgabe: icsvllvjnlktywuaroder eine andere gemeinsame Teilsequenz gleicher Länge

rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

Ausgabe: krkkoder eine andere gemeinsame Teilsequenz gleicher Länge

bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

Ausgabe: codeoder eine andere gemeinsame Teilsequenz gleicher Länge

nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

Ausgabe: golfoder eine andere gemeinsame Teilsequenz gleicher Länge

epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

Ausgabe: die leere Zeichenfolge

CJam, 31

q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

Probieren Sie es online aus

9 Bytes Golf dank Dennis!

Erläuterung:

Dieser Algorithmus versucht jedes mögliche Zeichen für die erste Position der Teilsequenz, ersetzt jede Zeichenfolge nach dem ersten Auftreten dieses Zeichens durch die Teilzeichenfolge und ruft sich dann rekursiv auf (mit Memoisierung).

q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string

Python - 665 644

Einrückungsstufen:

1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

Der Code definiert eine Funktion o, die eine Liste von Zeichenfolgen als Argumente verwendet und eine der LCS für die Zeichenfolgen zurückgibt.

def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

Testcode:

tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

Zeit, die benötigt wird, um die Tests auf meinem Computer auszuführen:

$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys

Pyth, 59 58 55 35 Bytes

L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

Schneiden Sie dank @isaacg satte 20 Bytes!

55-Byte-Version:

DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Schneiden Sie 3 Bytes ab, indem Sie .U@bZzu @F(dem Faltoperator) wechseln .

58-Byte-Version:

DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Schneiden Sie ein Byte ab, indem Sie das Format einer booleschen Bedingung ändern.

59-Byte-Version:

DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Das war schwer! Python hat immer wieder Fehler gemacht! Ich bin mir ziemlich sicher, dass es eine Art Fehler war, aber ich konnte keinen minimalen Testfall bekommen. Naja.

Ich habe den Algorithmus auf diesem basiert . Was in Ordnung ist, außer dass diese nur für zwei Saiten ausgelegt ist. Ich musste es ein wenig optimieren, damit es mehr funktioniert. Dann dauerte der letzte Testfall zu lange, sodass ich eine zusätzliche Prüfung hinzufügen musste, um die Rekursion zu beenden, wenn keine gemeinsamen Zeichen mehr vorhanden sind.

Es ist ziemlich langsam, sollte aber (hoffentlich) weniger als eine Stunde dauern. Ich teste auf meinem Core i3 mit 6 GB RAM, daher sollte Ihr 16 GB Core i7 dies durchbrechen. :) :)

Ich habe auch Pyth's Auto-Memoizing-Funktionen genutzt, um es ein bisschen schneller zu machen.

EDIT : @ Tennis sagte, es geht vorbei!

Fügen Sie zum Testen die folgende Zeile hinzu:

CQ

und geben Sie ihm eine Liste von Zeichenfolgen über Standardeingabe (z ['a', 'ab']. B. ).

Erläuterung zur 35-Byte-Version:

WIP.

Erläuterung zur 55-Byte-Version:

DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off

C 618 564 Bytes

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Und hier wird es für "Lesbarkeit" enträtselt:

d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

Meine Damen und Herren, ich habe einen schrecklichen Fehler gemacht. Es verwendet bisschen besser zu sein ... Und gehe weniger ... Spätestens jetzt ist es schnell .

Wir definieren eine rekursive Funktion L, die ein Array svon Zeichenarrays und die Anzahl nder Zeichenfolgen als Eingabe verwendet. Die Funktion gibt die resultierende Zeichenfolge an stdout aus und gibt im Übrigen die Größe in Zeichen dieser Zeichenfolge zurück.

Die Vorgehensweise

Obwohl der Code kompliziert ist, ist die Strategie hier nicht allzu komplex. Wir beginnen mit einem eher naiven rekursiven Algorithmus, den ich mit Pseudocode beschreiben werde:

Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if 

return best_length

Nun, dieser Algorithmus alleine ist ziemlich grausam (kann aber in ungefähr 230 Bytes passen, wie ich gefunden habe). So erhält man keine schnellen Ergebnisse. Dieser Algorithmus skaliert unglaublich schlecht mit der Stringlänge. Dieser Algorithmus ist jedoch skaliert ziemlich gut mit einer größeren Anzahl von Strings. Der letzte Testfall würde praktisch sofort gelöst, da keine Zeichenfolgen sZeichen cgemeinsam haben. Es gab zwei Haupttricks, die ich oben implementiert habe und die zu einer unglaublichen Geschwindigkeitssteigerung führten:

• LÜberprüfen Sie bei jedem Anruf bei , ob wir zuvor dieselbe Eingabe erhalten haben. Da in der Praxis wird über Zeiger auf den gleichen Satz von Saiten Informationen herumgereicht, haben wir nicht wirklich haben Strings zu vergleichen, nur Orte, die groß ist. Wenn wir feststellen, dass wir diese Informationen bereits erhalten haben, müssen wir die Berechnungen nicht durchgehen (meistens, aber das Abrufen der Ausgabe macht dies etwas komplizierter), und wir können davonkommen, indem wir nur die Länge zurückgeben. Wenn wir uns nicht ein Spiel finden, speichert diesen Satz von Eingabe / Ausgabe für künftige Anrufe zu vergleichen. Im C-Code versucht die zweite forSchleife, Übereinstimmungen mit der Eingabe zu finden. Bekannte Eingabezeiger werden in gespeichert Rund die entsprechenden Längen- und Zeichenausgabewerte werden in gespeichertA. Dieser Plan hatte drastische Auswirkungen auf die Laufzeit, insbesondere bei längeren Zeichenfolgen.

• Jedes Mal, wenn wir die Standorte von cin sfinden, besteht die Möglichkeit, dass wir sofort wissen, dass das, was wir gefunden haben, nicht optimal ist. Wenn jede Position cerscheint nach einigem bekannten Standort eines anderen Briefes, wir wissen automatisch , dass dies cnicht zu einer optimalen Teilkette führt, weil Sie einen weiteren Buchstaben in ihm passen. Dies bedeutet, dass wir für geringe Kosten möglicherweise mehrere hundert Anrufe Lfür große Zeichenfolgen entfernen können . Im obigen C-Code yist ein Flag gesetzt, wenn wir automatisch wissen, dass dieses Zeichen zu einer suboptimalen Zeichenfolge führt, und zist ein Flag gesetzt, wenn wir ein Zeichen finden, das ausschließlich früher als jedes andere bekannte Zeichen erscheint. Die aktuell frühesten Erscheinungen von Zeichen werden in gespeichertx. Die derzeitige Umsetzung dieser Idee ist etwas chaotisch, hat aber in vielen Fällen die Leistung nahezu verdoppelt.

Mit diesen beiden Ideen dauerte das, was in einer Stunde nicht fertig war, ungefähr 0,015 Sekunden.

Es gibt wahrscheinlich noch viel mehr kleine Tricks, die die Leistung beschleunigen können, aber zu diesem Zeitpunkt begann ich mir Sorgen um meine Fähigkeit zu machen, alles zu spielen. Ich bin immer noch nicht zufrieden mit dem Golf, also werde ich wahrscheinlich später darauf zurückkommen!

Timings

Hier ist ein Testcode, den ich einlade, online zu testen :

#include "stdio.h"
#include "time.h"

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));


    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

Ich habe die Testfälle des OP auf einem Laptop ausgeführt, der mit einem 1,7-GHz-Intel Core i7-Chip mit einer Optimierungseinstellung von ausgestattet ist -Ofast. Die Simulation ergab einen Spitzenwert von 712 KB. Hier ist ein Beispiellauf für jeden Testfall mit Zeitangaben:

Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s


Total time: 0.062293 s

Beim Golfen habe ich die Leistung ziemlich stark beeinträchtigt, und da die Leute die rohe Geschwindigkeit (0,013624 s, um alle Testfälle zusammen abzuschließen) meiner vorherigen 618-Byte-Lösung zu mögen schienen, lasse ich sie hier als Referenz:

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Der Algorithmus selbst bleibt unverändert, aber der neue Code basiert auf Unterteilungen und einigen schwierigeren bitweisen Operationen, die das Ganze verlangsamen.

Python 2, 285

Code:

import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

Verwendung:

print f('',[],['axbycz','xaybzc'])

Erläuterung:

Dies ist eine rekursive Funktion. sist der Charakter, den wir suchen. aenthält eine Liste der nachgeschnittenen Zeichenfolgen s. benthält eine Liste der noch nicht gehandelten Zeichenfolgen. fGibt die längste gemeinsame Zeichenfolge zurück.

Die erste Bedingung prüft, ob wir alle Zeichenfolgen durchlaufen haben. Wenn ja, bedeutet dies, dass es sich sum ein gemeinsames Zeichen handelt, und es kehrt zurück sund sucht nach häufigeren Zeichen.

Die zweite Bedingung prüft, ob wir keine Zeichenfolge durchlaufen, was bedeutet, dass wir nicht einmal ein Zeichen haben ( a==[]entspricht s==''). Wenn ja, überprüfen wir jedes Zeichen der ersten Zeichenfolge in b.

Die letzte Zeile bewegt den ersten String in bzu a, indem jedes Vorkommen zu finden , sin dieser Zeichenfolge.

Beim ersten Aufruf ssollte die Zeichenfolge leer sein. asollte eine leere Liste sein und bsollte alle Zeichenfolgen enthalten.