Moin basti,
ich denke, es geht weniger um ein programmiertechnisches Problem,
als vielmehr um ein logisches (zumindest soweit ich's momentan begreife).
Zunächst einmal könnte man ja sagen: suche alle substrings, die in
beiden strings identisch sind.
Wenn die Identitaeten gefunden sind, vergleiche die jeweils wieder mit
den beiden Eingabestrings, und pinsel alles, das nicht übereinstimmt, bunt an -
im ersten string lila, im zwoten tschidscheringrün.
Das kann man mit ein paar Schleifen machen, mit Rekursionen, unter
Zuhilfenahme von Stringfunktionen oder regexes, oder von allem etwas,
ad libitum.
Nun gibt es aber diverse Arten denkbarer Unterschiede <=> Gleichheiten.
In Deinem Beispiel geht es um Einfügungen. Möglich sind aber auch zB.
Verdopplungen (oder auch mehrfache Wiederholungen) oder, wie bereits
erwähnt, Umstellungen, oder Kombinationen aus allem.
Während der Fall der einfachen Einfügung relativ leicht zu behandeln ist,
(im folgenden der Vergleich von a und b), ist der Vergleich
von c und d schon etwas unklarer. Ich habe da den substring Ubbu_ubbu,
gemeinerweise in beiden zu vergleichenden strings doppelt vorkommend.
Was ist nun unter 'Unterschied' zu verstehn? Das hängt, soweit ich das
sehn kann, davon ab, was man unter 'Unterschied' verstehn möchte bzw. in
Abhängigkeit der jeweiligen Aufgabenstellung verstehen muß/soll.
Ich habe das folgende Beispiel in python gemacht, einfach deshalb,
weil mir a) php nicht so geläufig ist, und b) python-scripts beinah wie
pseudo-code gelesen werden können (wenn man sich python nicht runterladen
möchte und einfach ausprobieren). Ich denke, Du wirst damit keine
Verständnisschwierigkeiten haben:
# coding: utf-8
from string import *
a = """
Aber das währe doch nicht nötig gewesen.
Es ist nämlich so, daß hier alles automatisch erledigt wird,
aber das wissen Sie ja.
"""
b = """
'Aber das wäre doch nicht nötig gewesen', antwortete er.
'Es ist nämlich so, dass hier alles automatisch erledigt wird,
aber das wissen Sie ja.'
"""
####################################
c = """hjmmn,,.,....oo
Aber das währe doch nicht nötig gewesen.
Ubbu_ubbu
Es ist nämlich so, SSSSSSSSSSSSdaß hier alles automatisch erledigt wird,
aber das wissen Sie ja.Ubbu_ubbu
nmoziooppp
"""
d = """ qweeeeee
'XXXXXXnötig gewesen', antwortete er. nqwnenrtnnn65656Ubbu_ubbu5656
'Es ist nämlich so, dass hier alles automatisch erledigt wird,
aber das wissen Sie ja.'Aber hmurgknurgldas wäre doch nicht
8iiljk..%%%%%%%%%%Ubbu_ubbu%%%%%%%%%
"""
###################################################################
def V(s1, s2, d = 0): # d soll 0 oder -1 sein
v, ve, a = [[0, 0, 0, '']], [0, 0, 0, ''], 0
if len(strip(s1)) <= len(strip(s2)): s1, s2 = map(strip, (s1, s2))
else: s1, s2 = map(strip, (s2, s1))
while a < len(s1):
o, iq = a + 1, 0
while o < len(s1):
try:
i = index(s2, s1[a:o])
ve = [i, a, len(s1[a:o]), s1[a:o]]
except:
s = s1[a:o-1]
for j in v:
if find(j[3], s) > d: iq = 1
if len(s) and not iq: v.append([i, a, len(s), s])
else: iq = 0
break
o += 1
a += 1
if v[-1][0] < ve[0] and find(v[-1][3], ve[3]) < 0: v.append(ve)
return v[1:]
def N(n):
for i in range(len(n)): #eine moegliche normalisierung, wenn keine
try: #vertauschungen vorliegen
if n[i][0] > n[i+1][0]: n.remove(n[i])
except: pass
return n[n.index(min(n)):n.index(max(n))+1]
print 'n___________________________G1_______________________________n'
G1 = V(a, b)
for i in G1: print i
print 'n___________________________G1_N_____________________________n'
G1_N = N(V(a, b))
for i in G1_N: print i
print 'n___________________________G2_______________________________n'
G2 = V(c, d)
G2.sort() # eine moeglichkeit, sich nen ueberblick zu verschaffen
for i in G2: print i
print 'n______________________aus die maus__________________________n'
Das erzeugt die Ausgabe:
___________________________G1_______________________________
[1, 0, 11, 'Aber das wxe4']
[18, 11, 1, 'h']
[12, 12, 27, 're doch nicht nxf6tig gewesen']
[55, 39, 6, '.n ']
[62, 45, 21, 'Es ist nxe4mlich so, da']
[85, 67, 65, ' hier alles automatisch erledigt wird,n aber das wissen Sie ja']
___________________________G1_N_____________________________
[1, 0, 11, 'Aber das wxe4']
[12, 12, 27, 're doch nicht nxf6tig gewesen']
[55, 39, 6, '.n ']
[62, 45, 21, 'Es ist nxe4mlich so, da']
[85, 67, 65, ' hier alles automatisch erledigt wird,n aber das wissen Sie ja']
___________________________G2_______________________________
[10, 15, 5, 'n ']
[10, 60, 5, 'n ']
[10, 74, 5, 'n ']
[22, 4, 1, 'n']
[22, 46, 13, 'nxf6tig gewesen']
[36, 5, 1, ',']
[36, 6, 1, ',']
[36, 8, 1, ',']
[42, 13, 1, 'o']
[42, 14, 1, 'o']
[51, 7, 1, '.']
[51, 12, 1, '.']
[51, 59, 1, '.']
[69, 65, 9, 'Ubbu_ubbu']
[69, 179, 9, 'Ubbu_ubbu']
[88, 79, 19, 'Es ist nxe4mlich so, ']
[93, 44, 3, 't n']
[97, 2, 1, 'm']
[97, 3, 1, 'm']
[97, 194, 1, 'm']
[101, 0, 1, 'h']
[101, 31, 1, 'h']
[111, 113, 43, ' hier alles automatisch erledigt wird,n ']
[151, 152, 27, ' aber das wissen Sie ja.']
[156, 21, 9, 'ber das w']
[170, 97, 2, ' S']
[175, 1, 1, 'j']
[179, 20, 5, 'Aber ']
[195, 25, 6, 'das wxe4']
[201, 32, 14, 're doch nicht ']
[227, 9, 2, '..']
[227, 10, 2, '..']
[227, 11, 2, '..']
______________________aus die maus__________________________
Aufgelistet werden die beiden offsets, die Länge des gemeinsamen substrings,
und eben jenner.
Wie Du in Liste G2 unter zB. den Einträgen Ubbu_ubbu sehn kannst, habe ich
jetzt nur nach dem niedrigsten index im zwoten string suchen lassen,
eben aus oben erwähntem Grund: wenn man auch nach andern indices sucht,
welche Änderung im zwoten string wäre welcher Stelle im ersten string
zuzuordnen? Und daraus ergibt sich die Frage: Wenn verschiedene Änderungen
vorliegen, welche ist bezüglich des Originals einerseits und im Vergleich
zueinander andrerseits als Änderung aufzufassen, und welche 'Änderung' ist
gar keine, sondern eigentlich 'gleichgeblieben'.
Vermutlich sollte man einen 'willkürlich' festzusetzenden Bezugspunkt wählen,
an dem dann die anderen Punkte nach Bedarf gemessen werden.
Naja, vielleicht bringt's Dich ja auf ein paar klügere Gedanken als mich.
gruß
matho