\(T\) に対する操作の結果得られうる文字列からなる集合を \(f(T)\) で表します。また、 \(f(T)\) のサイズが \(1\) のとき、\(T\) に対する操作の結果得られる文字列を \(g(T)\) で表します。

必要十分条件の考察

まずいずれかの \(S_j\ (i\neq j)\) を部分文字列に含むような \(S_i\) について考えます。この \(S_i\) に対し \(S_j\ (j \neq i)\) を前から貪欲に除くことで空文字列にできる場合、 \(S_i\) の有無によって \(f(T)\) は変化しません。よって判定の際はそのような \(S_i\) を除いてかまいません。空文字列にできない場合は \(S_i\) が「悪い文字列」になります。

上記のような処理を行った後、まだ「悪い文字列」が見つからない場合、任意の \(S_i,\ S_j\ (i\neq j)\) について \(S_j\) は \(S_i\) の部分文字列になりません。このとき、「悪い文字列」が存在しない必要十分条件は以下のようになります。

• 文字列 \(A,\ B,\ C\ (A\neq C)\) および \(1\leq i,\ j \leq n\) であって、\(S_i=A+B,\ S_j=B+C\) を満たすものが存在しない。

証明

• 必要性

上記のような \(A,\ B,\ C\) および \(i,\ j\) が存在するものとします。まず \(A,\ C\) が \(S_k\) のいずれかを部分文字列に含むとすると \(S_i,\ S_j\) が \(S_k\) を部分文字列に含んでしまいます。よって \(A,\ C\) は \(S_k\) のいずれも部分文字列に含まず、 \(f(A)=\{A \},\ f(C)=\{C \}\) となります。このため、 \(\{A,\ C\} \subset f(A+B+C)\) となり、\(A\neq C\) より \(T=A+B+C\) は「悪い文字列」となります。

• 十分性

任意の \(T\) に対し \(f(T)\) のサイズが \(1\) であることを \(|T|\) についての帰納法で示します。まず \(T\) が空文字列のときは明らかです。
次に \(T\) より短い文字列について \(f(T)\) のサイズが \(1\) であるとします。 \(T\) から \(S_i,\ S_j\) をある位置から除いて得られる文字列をそれぞれ \(T'_1,\ T'_2\) と置きます。\(g(T'_1)=g(T'_2)\) であることを示せばいいです。 \(S_i,\ S_j\) を取り除く位置に重なりがある場合は上の条件から \(T'_1=T'_2\) が言えるので \(g(T'_1)=g(T'_2)\) です。 \(S_i,\ S_j\) を取り除く位置に重なりがない場合、 \(T\) から \(S_i,\ S_j\) を両方除いて得られる文字列 \(T'_3\) が取れ、\(g(T'_1)=g(T'_2)=g(T'_3)\) が成り立ちます。

よってこの問題を解くにあたっては

• Part1: 長さが \(S_i\) より短いような \(S_j\) のみを操作に用いて \(S_i\) を空文字列にできるような \(S_i\) の除外
• Part2: 上記の必要十分条件を満たすかの判定

が行えればいいです。

Part1

空文字列に \(S_i\) を \(1\) 文字ずつ追加し、末尾が \(S_j\) のいずれかに一致したら除くことで判定します。 これは Aho-Corasick 法を用いた文字列検索を用いることで \(O(|S_i|)\) 時間で行えます。ただし、通常の文字列検索のように failure-link を用いてノード間の移動を行う場合、 \(\Theta(|S_i|)\) だけかかる移動を何度も行ってしまうことがあります（\(S=\{\) AAA…AAA, C, BD, AAA…ABDCCC…CA\(\}\) のケースなど）あらかじめすべてのノードに対してすべての文字が来た場合の移動先を求めておきましょう。failure-link を求めるのと同じ要領で \(O(\sigma \sum_{i=1}^{N}|S_i|)\) で計算できます。

Part2

\(S_i\) の長さ \(n\) の suffix と \(S_j\) の prefix が一致するような \(j\) を \((i,\ n)\) ごとに記録します。これは Aho-Corasick 法を適用した Trie 木上で最後まで移動した後、failure-link をたどり続けることで \(O(|S_i|)\) で列挙できます。同じ suffix に対し \(2\) つ以上の \(S_j\) の prefix が一致した場合は明らかに条件を満たさないので記録する \(j\) は高々 \(1\) 個としていいです。
\((i,\ n)\) に対し \(j\) が記録されている場合、条件を満たすかチェックするには \(|S_i|=|S_j|\) であり \((j,\ n-|S_i|)\) に \(i\) が記録されているかを確認すればいいです。

以上よりこの問題は \(O(\sigma \sum_{i=1}^{N}|S_i|)\) で解くことができます。