Edytuj odległość między dwoma wyrażeniami regularnymi

Question

Napotkałem to pytanie w wywiadzie:

Przy dwóch wyrażeń regularnych obliczyć odległość edycji między nimi. Odległość edycji jest definiowana jako najmniejsza odległość edycji między dowolnymi dwoma ciągami wygenerowanymi odpowiednio przez dwa wyrażenia regularne.

Formalnie, szukamy d(L1,L2) = min { d(x,y) | x from L1, y from L2 }, gdzie L1 i L2 są językami wygenerowanymi przez dwa wyrażenia regularne.

Nie udało mi się rozwiązać tego problemu podczas wywiadów. Nawet teraz nie mam pojęcia, jak go rozwiązać. Jakieś pomysły?

myślę, że to jest taki sam jak http://www.spoj.com/problems/AMR10B/

Answer 1

Jest maszyny państwowe skończonych, które reprezentują dwa języki. Powiedzmy, że pierwszy język ma stany S [1], S [2], ..., S [N1] i przejścia c: S [i] -> S [j] (co oznacza stan i przechodzi do stanu j pod wprowadzonym znakiem c) i T [1], T [2], ... T [N2] dla drugiego języka (z własnym zestawem przejść).

Teraz można skonstruować ważony wielo-wykres z węzłami będącymi parami stanów i krawędziami między parami (S [i1], T [i2]) -> (S [j1], T [j2]), jeśli każdy z tych czterech przypadków obejmuje:

• Istnieje c: S [i1] -> S [j1] i i2 = j2. To ma masę 1
• Istnieje c: T [i2] -> T [j2] i i1 = j1. To ma masę 1
• Istnieje c: S [i1] -> S [j1] i c: T [i2] -> T [j2]. To ma wagę 0
• Istnieje c: S [i1] -> S [j1] i d: T [i2] -> T [j2]. To ma wagę 1

Następnie, znalezienie najniższej ścieżki masy od pary stanów początkowych do dowolnej pary stanów akceptujących daje minimalną odległość edycji.