[python] Comparare due stringe e ottenere la sub-string piu grande uguale

[Hardcore]

Capisco che il titolo sia criptico, ma un piccolo esempio chiarirà tutto:

stringa1= "Windows_LiveMessenger"
Stringa2="MsnMessenger"

Vorrei trovare un metodo che mi ritorni "Messenger"

Se avessi:
Stringa1:"Microsoft_Messenger"
Stringa2:"Messenger_Messenger"

Vorrei ottenere "_Messenger"

C'è qualche cosa di già presente o devo scrivere del codice a mano?

[Rise-the-Sky]

Il tuo problema è stato semplicemente il trovare la giusta definizione di quello che ti serviva ^^.

Quello che cerchi è la Longest common subsequence (LCS), che è un algoritmo abbastanza trattato in ambito teorico percui in giro si trovano codici di soluzione già scritti.

ES:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring

[Hardcore]

Ho implementato l' LCS, e la cosa sembra funzionare correttamente. Però vi sono casi in cui l' LCS si rivela inadeguato, ho visto che esistono alcuni algoritmi relativi allo String Matching. (Trovato uno detto Bitap), vorrei sapere se ne conoscete altri.

Per essere precisi il caso in cui LCS ha una criticità è il seguente:

Stringa1: Samsung
Stringa2: SamTung

LCS mi ritorna come SubString piu grande una di dimensione 3: (sam oppure ung).
In realtà le due stringhe sono molto simili, differiscono solo per una lettera.

[Rise-the-Sky]

Scusa ma questa non è una criticità del LCS..che nel tuo esempio ti restituisca san è perfettamente corretto secondo quanto avevi chiesto nel post iniziale.

Dunque il problema torna a essere lo specificare cosa ti serve precisamente.

Ad esempio..proprio in quell'esempio Samsung / SamTung , cosa dovrebbe restituirti l'algoritmo che desideri?

[Axet]

Stai facendo confusione, as usual :D

La richiesta che fai nel primo reply e quella che hai fatto in seguito sono diverse tra loro. Per la prima il LCS è perfetto, come ti ha già spiegato risethesky. Per la seconda.. è una distanza di edit (o se lo vuoi vedere in termini binari una distanza di hamming).
Però devi chiarificare cosa vuoi fare, se una o l'altra cosa (o entrambe), perchè si tratta di problemi differenti a cui fanno capo soluzioni differenti

[Eltarion]

Stai facendo confusione, as usual :D

La richiesta che fai nel primo reply e quella che hai fatto in seguito sono diverse tra loro. Per la prima il LCS è perfetto, come ti ha già spiegato risethesky. Per la seconda.. è una distanza di edit (o se lo vuoi vedere in termini binari una distanza di hamming).
Però devi chiarificare cosa vuoi fare, se una o l'altra cosa (o entrambe), perchè si tratta di problemi differenti a cui fanno capo soluzioni differenti

minchia quanto mi ecciti quando parli così!!!!

:sneer:

[San Vegeta]

io sono dell'idea che se seguisse un corso di programmazione di base e algoritmi, queste idee confuse non ci sarebbero
però sono polemico come al solito :(

[Eltarion]

ma dai, una persona si interessa all'arte della programmazione e voi gli tarpate le ali così? Dovreste essere contenti di aiutare qualcuno a maneggiare l'Antica Arte.

[Rise-the-Sky]

ma dai, una persona si interessa all'arte della programmazione e voi gli tarpate le ali così? Dovreste essere contenti di aiutare qualcuno a maneggiare l'Antica Arte.

In realtà quello che viene fuori qui cmq non è un problema di programmazione, ma un problema di analisi.
E se per diventare un programmatore skillato normalmente la pratica è sufficente (unita a una predisposizione naturale al pensiero logico...), per diventare un buon analista un po' di teoria è consigliabile.

[Axet]

Ehm vi state confondendo con brcondor che non fa informatica. Magari mi sbaglio eh, ma se non erro hardcore fa ingegneria informatica

[Rise-the-Sky]

Ehm vi state confondendo con brcondor che non fa informatica. Magari mi sbaglio eh, ma se non erro hardcore fa ingegneria informatica

Questo non deporrebbe a favore delle sue conoscenze di algoritmi :hidenod:

(pura trollata da Informatico puro ovviamente :sneer: )

[Hador]

non c'è nessun corso che ti insegni a capire cosa minchia vorresti fare :sneer:

[Eltarion]

appunto anche se studia informatica che problema c'è? Se sapesse, non chiederebbe no?

[San Vegeta]

fa benissimo a chiedere perchè ha voglia di imparare. Però stiamo parlando di problemi "banali" e ci sono lacune persino nell'identificare il problema. Il linguaggio di programmazione è uno strumento: se devi fare una spada, sai che ti serve una fucina del minerale, un incudine e un martello (almeno); ma sapere quale strumento ti serve non ti fa forgiare una spada.

spero sia più chiaro, altrimenti amen... :P

fortunamente ci sono maree di tutorial e guide che questi problemi li affrontano bene, però serve tempo per trovarli e leggerli...