Ein Problem über Algorithmus von String, dp, Graph oder etw.

Question

Problem folgt.

1. über "schön"

   1) "ab" schön

   2) Ein schön => "a" + A + "b" ist schön

   3) A und B sind schön => A + B ist schön

2. über "~"

   1) "ab" ~ "ab"

   2) A ~ B => "a" + A + "b" ~ "a" + B + "b"

   3) A ~ B und C ~ D => A + C ~ B + D und A + C ~ D + B

jetzt gibt es höchstens 1000 Reihe von ‚a‘ und ‚b‘ eine Menge S bilden, finden Sie die größte Teilmenge von S in dem jedes Element schön und keiner sein muss Das Paar (A, B) enthält A ~ B. Gib die Kardinalität aus.

Es gibt einige Unterschiede zu den Problemen, die ich vorher gesehen habe: A + B + C + D + A + C + B + D + B + D + A + C, aber A + B + C + D + B + D + A + C hält nicht.

Zwei Schwierigkeiten für mich:

1. , wie Sie überprüfen, ob S1 ~ S2
2. , wenn ich jedes Paar "~" wissen, wie kann ich die Mächtigkeit

mehr Details: https://www.spoj.pl/problems/ABWORDS/

Answer 1

Die Regeln für die Konstruktion eines netten Wortes implizieren, dass jedes nette Wort mit "a" beginnt und mit "b" endet. Daher gibt es eine eindeutige (bis Sequenzing - Regel 3) Dekomposition eines netten Wortes in nette Unterwörter: finde alle "ab" s, und versuche dann, sie mit Regel 2 zu erweitern, und folge sie mit Regel 3. Wir kann diese Zerlegung über einen Baum ausdrücken (n Zweige zur wiederholten Anwendung von Regel 3).

Im Baumkontext drückt die "~" Relation einfach isomorphe Bäume aus, denke ich (wobei die Verzweigungsreihenfolge keine Rolle spielt).

BEARBEITEN: wie bereits erwähnt, spielt die Reihenfolge der Zweige eine Rolle.

Ich werde versuchen, das Problem zu lösen, wie im ursprünglichen Link angegeben (die 2 Definitionen von "nett" stimmt nicht überein).

Zuerst Ähnlichkeit zwischen zwei Wörtern X und Y, mit DP.

Definieren Sie f(a, b, n) als die Funktion, die angibt, dass X[a..a+2n-1]Y[b..b+2n-1] ähnlich ist und dass beide Unterwörter nett sind.

f(a, b, 0) = 1. 

für n> 0,

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n) 
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1) 
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k) 
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k) 

Ich denke, diese ist O (n^4) (urgh).

Für den zweiten Teil, wenn Sie die Wörter als ein Graph mit Kanten darstellen, die die Ähnlichkeitsrelation darstellen, versuchen Sie im Wesentlichen, die maximale unabhängige Menge zu finden, denke ich. Wenn ja, viel Glück! Es ist NP-hart (dh keine bekannt bessere Lösung als alle Kombinationen zu versuchen) im allgemeinen Fall, und ich sehe keine Eigenschaften, die es leichter in diesen machen :(

EDITED, um die Definition zu machen die Ähnlichkeit automatisch Nettigkeit prüft es ist ganz einfach

EDITED noch einmal wegen meiner Dummheit