Codeforces ラウンド #244 (ディビジョン 2)D (サフィックス オートマトン)_html/css_WEB-ITnose

Codeforces Round #244 (Div. 2)D (Suffix Automata)

(0 とラベル付けされたノードは null ノードである必要があり、いかなる場合も使用できません。覚えておいてください、今後同じ間違いを繰り返すことはできません)

これ 質問で接尾辞オートマトンが使用されている場合は、接尾辞オートマトンの多くのプロパティを十分に深く理解していることになります。サフィックス配列の作り方は面倒なので考えていません。 。 。 。

質問: 長さが 5000 を超えない 2 つの文字列 s1 と s2 がある場合、これら 2 つの文字列に 1 回だけ現れる最も短い共通部分文字列を見つけます。

問題解決のアイデア: 探しているのは共通の部分文字列であり、出現数には制限があります。最初のアイデアは、接尾辞オートマトンは、 の出現数を処理するのに最適です。部分文字列。方法は次のとおりです。まず s1 の sam を確立し、トポロジー dp を使用して各ノードの代表文字列の出現数を見つけます。目的は何ですか?実際、ok[i][j]、つまり部分文字列 s1[i] ~ s1[j] が 1 回のみ出現するかどうかを調べたいのです。代表文字列の出現回数はわかったので、この ok[i][j] はどうやって求めるのでしょうか?確立されたオートマトンでの一致には s1 を使用します。現在の一致は s1[i] です。レコード temp は、現在の一致の最長の長さを示し、現在の一致がどのノードにあるかを示します。ここには AC オートマトンに非常によく似たプロパティがあります。now が一致すれば、間違いなく fa[now] と一致します。次に、上に進み、出現回数が 1 より大きい最初のノード p を見つけます。その後、 i で終わり、 val[p]+1 から temp までの長さの部分文字列は s1 に 1 回だけ出現する必要があります。これを ok 配列に記録します。 2 番目のステップは s2 を処理することです。これも同じプロセスです。sam を作成し、各ポイントの代表的な文字列 (cnt[] 配列) の出現数を見つけます。 3 番目のステップは、s1 を使用して s2 の sam を照合することです。照合プロセスは、s1 の ok 配列の最長の長さを見つけます。 s2 内の cnt が 1 より大きい最初のノード p の場合、現在一致する部分文字列の末尾で終わる部分文字列の長さは val[p] + 1 から temp までです。この文字列は s2 に 1 回だけ出現する必要があります。次に、val[p] + 1 から temp までの j を列挙します。それが s1 にあり、i で終わる場合、長さ j の部分文字列は 1 回だけ現れます (つまり、ok[i-j+1][i] = = 1)。 )、この j が答えになる可能性があり、それを使用して ans を更新します。

コード:

rree