Wie bekomme ich alle verschiedenen Teile in zwei Arrays?

Question

Angenommen, ich habe einen Satz:

When Grazia Deledda submitted a short story to a fashion magazine at the age of 13 

dieser Satz in zwei Listen aufgeteilt:

# list 1 
[When] [Grazia Deledda] [submitted a short story] [to] [a] [fashion magazine] [at] [the age of] [13] 
# list 2 
[When] [Grazia Deledda] [submitted] [a short story] [to] [a fashion] [magazine at] [the age of] [13] 

Jetzt mag ich die verschiedenen Teile in diesen zwei Array erhalten, dieses Ergebnis sollte des Beispiels sein:

[ 
    ([[submitted a short story]],[[submitted] [a short story]]), 
    ([[a] [fashion magazine] [at]], [[a fashion] [magazine at]]) 
] 

so sollte es erfüllen diese Anforderungen:

• jedes Paar den gleichen Inhalt, zum Beispiel haben sollte: [[submitted a short story]] verbunden sein kann, in 'submitted a short story' und [[submitted] [a short story]] kann auch Position die gleichen Start hat in 'submitted a short story'

• jedes Paar Position und Ende zusammengefügt werden sollte Zum Beispiel: [[submitted a short story]] der beginnt bei 3 und endet mit 6. [[eingereicht] [eine Kurzgeschichte] sind die gleichen.

• das wichtigste ist, dass jeder sollte die kürzeste sein, zum Beispiel trifft [[submitted a short story] [to]] und [[submitted] [a short story] [to]] auch die ersten beiden Anforderungen, aber es ist nicht die kürzeste. ?

Jede Art und Weise O (n^2) Komplexität zu vermeiden

Answer 1

ich falsche Richtung kann am Anfang bekommt, kann diese Frage leicht sein, denke ich habe eine gute Idee:

#!/usr/bin/env python 
# encoding: utf-8 

# list 1 
llist = [["When"], ["Grazia", "Deledda"], ["submitted", "a", "short", "story"], ["to"], ["a"], ["fashion", "magazine"], ["at"], ["the", "age", "of",], ["13"],] 
# list 2 
rlist = [["When"], ["Grazia", "Deledda"], ["submitted"], ["a", "short", "story"], ["to"], ["a", "fashion"], ["magazine", "at"], ["the", "age", "of",], ["13"],] 

loffset = -1 
roffset = 0 
rindex = 0 
lstart = -1 
rstart = -1 
for lindex, litem in enumerate(llist): 
    if loffset == roffset and litem != rlist[rindex]: 
     lstart = lindex 
     rstart = rindex 
    loffset += len(litem) 
    while roffset < loffset: 
     roffset += len(rlist[rindex]) 
     rindex += 1 
    if loffset == roffset and lstart >= 0: 
     print(llist[lstart:lindex+1], rlist[rstart:rindex]) 
     lstart = -1