Informatyka UJ forum

Fen

mam pewne pytanko:

dokładnie chodzi mi o czytelne rozwiązanie problemu który pojawił się na drugiej kartkówce u Kecima:

mamy daną policzoną tablice KMP dla konkatenacji wzorca i tekstu. wyznaczyć wszystkie poprawne przesunięcia wzorca w tekście.

hansu

No wiec mamy ta tablice KMP. Bedziemy sobie tworzyc tablice o takiej samej dlugosci zlozona z zer i jedynek (czyli de facto tablice booli). Oznaczmy
W - wzorzec
T - tekst
WT - katenacja powyzszych.
w - dl wzorca
t - dl tekstu
A[] - nasza tablica.

A[i] == 1 oznacza ze w tekscie WT wystepuje W i konczy sie dokladnie na i-tej pozycji.

Inicjalizacja

Skrobocik

hansu

Nie mosci Skrobocie. Piszac 2w mam na mysli wlasnie 2w a nie 2w-1. Dlaczego?No bo jesli A[2w] == 1 to znaczy ze w polu 2w konczy sie wzorzec, czyli to znaczy ze zaczyna sie w w+1 czyli dokladnie na poczatku tekstu. (tekst jest indeksowany od 1 do t+w).

Azhag

Kecim mowil ze zrobi gdzies pkt za aktywnosci obecnosci .. wiecie gdzie to jest/ bedzie ?

Roxel

@Dudzio: na forum tcs jest wątek na ten temat

Skrobocik

Rogal

Rabina-Karpia wogóle nie musimy umieć?

Fidel

Fen

czy ktoś ma jakieś kody/dodatkowe materiały do Hopcrofta-Karpa? poza tym co jest na wykładzie...

kap00ch

to co jest na wykladzie + kartka + olowek jest wystarczajace do implementacji i zrozumienia dzialania w razie potrzeby nie wspominajac o IoD - Implementation on Demand

exeman

wytlumaczcie mi prosze, czy moje rozwiazanie jest poprawne? Jesli nie to prosze o kontrprzyklad.

Yoter

albo masz konflikt oznaczeń albo nie możesz użyć k bo nie masz jej na wejściu albo ja czegoś nie wiem...

exeman

O fuck. Myslalem, ze k mamy dane :P I mi sie to trywialne wydalo :P Ok, to ide robic to jeszcze raz.

exeman

Dobra, to prosze teraz o znalezienie kontrprzykladu na ponizsze rozwiazanie, ew. milo mi bedzie, jesli bedzie on poprawny :P

exeman

Eh, w takim razie bede wdzieczny za poprawne rozwiazanie :>

Fidel

u nas na cwiczeniach bylo takie zadanie:

mamy juz jakies skojarzenie w grafie dwudzielnym i trzeba sprawdzic czy jest to skojarzenie maksymalne, pamieta ktos jak to zrobic?

Spectro

hansu

@exeman:

Zalozenia: slowo W o dlugosci w

Teza:

(istnieja takie U i k ze W = U^k) <==> (w - KMP(w)) dzieli w

Dowod "<=" trywialny
Dowod "=>" tez trywialny, jesli sie zalozy ze U jest minimalne z mozliwych (czyli takie jakby "nieokresowe" - nie jest sklejeniem dwoch lub wiecej takich samych slow)

(sorki ze tak pisze skrotowo, ale to naprawde sa automatyczne dowody jak tylko sie to rozrysuje - a zapisanie tego zajeloby mi chwile)

Algorytm - no bez jaj :P

Fidel

a jak najlepiej ja policzyc sciezke powiekszajaca w tym przypadku? trzeba graf rezydualny tworzyc czy jest jakis ciekawszy sposob?

Rogal

@Fidel: Ja bym zrobił taki przejście jak jest w H-K, tj. takiego BFS-a zaczynając od wszystkich wierzchołków z lewej strony.

exeman

Fidel: a nie wystarczy raz Edmonds Karpa puscic? To zlozonosc liniowa by mialo, wiec brzmi obiecujaco moim zdaniem :>

Fidel

a mi sie wydaje ze to trzeba zrobic tak jak w wazniaku jest algorytm wyszukiwania sciezki rozszerzajacej dla grafu (bez zadnych przeplywow) wyklad:
[link widoczny dla zalogowanych]

przynajmniej cos takiego z cwiczen pamietam ze robienie z tego sieci przeplywowej byloby nieoptymalne, tam w wazniaku to jest dobrze wytlumaczone. robi sie tylko graf skierowany i szuka sciezki

Fen

no własnie: tam(czyli w algorytmie z wazniaka do znajdowanie ścieżki alternujacej) jest taki myk "usuń cykle z P tak aby P było ścieżką prostą" - jak to zaimplementować na przykład, to chyba nie jest jakies trudne?

Fidel