Segítségkérés játékon kívül

Szövegre kell? Vagy DNS szekvenciákhoz?

Na valahogy így néz ki:

Feldarabolod a 2 szöveget szavakra.
str1, str2
A mátrixod count(str1) x count(str2) -es lesz, a mátrix 0. sora és oszlopa 0-val van feltöltve.
A mátrix további elemei az alábbiak szerint töltődnek (bal fentről kezdve kell kitölteni):

Az [X,Y] hely értékének kiszámításához kell az [X-1, Y-1] értéke, ez módosúl a következők szerint:
Ha str1[X] == str2[Y] akkor növeled az [X-1, Y-1] értékét 2-vel, ha nem, akkor csökkented 1-el.
Ezen felül veszed az [X-1,Y] és az [X,Y-1] mezők értékét is, mindkettőt csökkented 1-1el. Az így kapott három érték közűl a legmagasabb lesz az [X,Y] helyen.

Az így feltöltött mátrix feldolgozása a következőképpen zajlik:
Mindíg a mátrix legmagasabb értékű pontjáról indul feldolgozás, minden esetben a [X-1,Y-1], [X-1,Y], [X,Y-1] mezők közül arra megy a feldolgozás tovább amelyiknek a legmagasabb az értéke. A bejárt mezőknek megfelelő szót (str1[X]) mindíg elrakja, ebből fog összeállni a két szöveg közti leghosszabb eggyezező rész (mindíg előre kell befüzni az eredmény stringbe).

Ez volt a kérdés? Vagy a matekjára vagy kiváncsi?

Tudtommal lehet benne negatív, és a fentiekből látszik a lényege:
összehasonlítja a 2 szöveg szavait mindet mindegyikkel, Mivel mindíg az előző összehasonlítás eredményét növeli csökkenti, így a leghosszabb egyezés végén lesz a legnagyobb érték. Innen szépen visszalépked, és összerakja a sztringet. Addig megy visszafelé, amíg 0-t nem talál, vagy el nem fogynak a szavak.

Igen feltöltéskor ebben az esetben ha <0 akkor 0-zni kell.
Az insert delete a következőt jelenti:
Ha nem átlóban halad a legnagyobb értéket követve a feldolgozás, az azt jelenti, hogy szó beszúrás, vagy szóhiány van az egyik str1-en. (ugye ha csak egyik irányba megy a feldolgozó nem átlósan -1,-1 irányba, akkor az egyik tengelyen azonos szón marad a következő vizsgálatkor is)
Ezért a feltöltéskor a [X-1,Y] mező értékét a Deletion, az [X,Y-1] mező értéket Insertion büntetéssel veszik figyelembe tehát így néz ki:

[X,Y] = max( ([X-1,Y] + Deletion), ([X,Y-1] + Insertion), [X-1,Y-1] + Match/Mismatch)

(én fentebb az Insertion, és Deletion büntetés értékét mindkettőt 1-re vettem):
4 fajta súlyozás van:
Match (ez az én példámban 2 volt)
Mismatch (ez -1)
Insert (ez -1)
Delete (ez is -1)

Mátrix

          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0   -1 -1   -1    -1
BENNE 0   -1 -2   -2    -2
EGY   0   -1  1    0    -1
PRÓBA 0   -1  0    3     2

          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0    0  0    0     0
BENNE 0    0  0    0     0
EGY   0    0  2    1     0
PRÓBA 0    0  1    4     3

Attól függ milyen eredményt szeretnél kapni. Minél nagyobb a „büntetés” az adott függvényen, annál kevésbé fogja tolerálni az adott eltérést. Ha nagyokat vonsz le insert, delete-re, akkor rövidebb de teljesen azonos szövegek is bekerülhetnek. Ha nem túl nagy levonás van insert, delete-re, akkor egy két szó eltérés még bele fog férni, ha egyébként a szöveg egyezik.

Nincs valakinek scribd acca véletlenül?Találtam pár könyvet, ami fenn van, és szívesen elolvasnám, de legalábbis problémás a dolog.

Kösz előre is!

Hátha valaki tud segíteni.
A kérdés az, hogy hogyan dönthető el GYORSAN két téglalapról, hogy van-e közös pontjuk. Mindkét téglalap élei 0 és 90 fokot zárnak be az X tengellyel. Adott a bal felső, és a jobb alsó sarkuk koordinátája. Fontos szempont a gyorsaság, tizedmásodpercenként többszáz összehasonlítást kell végezni. Csak olyan megoldás jöhet szóba, ami koordinátákkal dolgozik (tehát raszteren kitöltjük feketével az egyiket, ill másikat kékkel, és lesz-e közös rész nem játszik)

Köszi, közben hasonlóra jutottam, bár kicsit olcsóbb (most fejeztem be az implementálást):
A két téglalapnak akkor és csak akkor van metszete, ha a mindkét téglalapot befoglaló legkisebb téglalap (fentiek szerint a min(a_2,x_2), min(b_2,y_2) és max(a_1,x_1), max(b_1,y_1) koordinátákkal leírt) megfelelő élhosszai rövidebbek mint a két vizsgálandó téglalap élhosszainak összege.

Azaz

( max(a_1,x_1)-min(a_2,x_2) < ( ( a_1 - a_2 ) + ( x_1 - x_2 ) ) ) ÉS ( max(b_1,y_1)-min(b_2,y_2) < ( ( b_1 - y_2 ) + ( b_1 - y_2 ) ) )

Szerintem nagyságrendilag azonos költsége van a két megoldásnak, min, max tulajdonképpen behelyetesíthető egy-egy egyenlőtlenséggel.
De lehet hogy az (((a_2+a_1)/2) - ((x_2+x_1)/2)) < ((a_2-a_1) + (x_2-x_1)) / 2 ) ÉS ((b_2+b_1)/2) - ((y_2+y_1)/2)) < ((b_2-b_1) + (y_2-y_1)) / 2 )) olcsóbb ezeknél, főleg, hogy a 2vel osztás elhagyható mindenhol. (Ez ugye azt mondja, hogy összeérnek, ha a két téglalap középontjainak X illletve Y koordinátában mért eltérése kisebb mint az adott irányú élhosszak átlaga)