Python - wie finden Sie alle Schnittpunkte von zwei strings?

So finden Sie alle Schnittpunkte (auch genannt der längsten gemeinsamen Teilstrings) von zwei strings und Ihre Position in beiden Zeichenketten?

Zum Beispiel, wenn S1="never" und S2="forever" dann führte Kreuzung muss ["ever"] und seine Positionen sind [(1,3)]. Wenn S1="address" und S2="oddness" dann führte Kreuzungen sind ["dd","ess"] und Ihre Positionen [(1,1),(4,4)].

Kürzeste Lösung ohne Bibliothek ist vorzuziehen. Aber jede richtige Lösung ist auch willkommen.

  • Tun die Zeichenketten erscheinen an der gleichen position in beiden Zeichenketten (wie Sie in beide Beispiele)?
  • Nein, Sie kann auch in verschiedenen Positionen wie "nie" und "immer". Ich habe mich verändert Beispiel.
  • Was meinst du mit "alle Lösungen", wenn für "call" und "wall" die richtige Lösung ist ["all"] und nicht ["a", "al", "all", "ll", "l", "l"]? Meinst du alle die maximale Lösungen? Was ist die genaue definition hier?
  • Und haben Sie Sorge, über die Zeit-Komplexität, oder nicht so viel?
  • 1:ja, maximale Lösungen. 2:Nicht so viel. Nur eine Lösung, wenn möglich in Python.
  • es ist besser!! Aber wenn es keine ist, dann ist es auch Ok!
  • -0. Nicht ein fan von dieser bitte-schreiben-Codes-für-mich Fragen.
  • es ist einfach ein Interessantes problem, ich denke, es macht eine Menge Spaß, übung solcher Art von Problemen. Ich persönlich mag es sehr viel, und ich habe es gelöst schon, aber es ist interessant, wenn jemand ausdenken kann eine alternative Lösung.
  • Dann poste deinen code als Startpunkt.
  • Code golf & Programmierung Rätsel sind off-topic für diese Seite. Siehe codegolf.stackexchange.com.
  • Wie groß können die Saiten sein? Was ist die Komplexität der Lösung, die Sie wollen?
  • es kann so groß sein wie die python-string. Es ist die Komplexität ist nicht wichtig noch.
  • Ich habe entdeckt, ein perfekt wunderbare Methode, aber diese Seite ist nicht groß genug, um es zu halten. Wenn ernst, es ist sehr lang und langsam.

InformationsquelleAutor psihodelia | 2011-09-27
Schreibe einen Kommentar