Q&A
Tの文字種類の範囲はどの程度ですか？
前提・実現したいこと
文字列Sと文字列Tを入力し、Tのすべての文字を含むSの最小連続部分文字列を計算量O(n)で見つけるプログラムを作成しています。
ここでnはSの文字数です。
またS、Tはともにアルファベット
Tに文字の重複はありません
S内にT内のすべての文字を網羅するウィンドウがない場合は、空の文字列 "" を返し、網羅する連続部分文字列がある場合は、Sには必ず1つの固有の最小連続部分文字列しかないことが保証されています。
例えば、
入力
S = "ADOBECODEBANC", T = "ABC"
に対し、
"BANC"
を出力します。
0(n)で実行可能なアルゴリズムを教えていただきたいです。
発生している問題・エラーメッセージ
実装を試みたのですが、計算量が0(n^2)になってしまいます。
試したこと
動的計画法を用いた。
何が n なのか決めないとできないんじゃないでしょうか。
https://ja.wikipedia.org/wiki/%E6%9C%80%E9%95%B7%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E5%88%97%E5%95%8F%E9%A1%8C
説明不足で申し訳ありません.
S,T共にアルファベット
Tは同じ文字が重複しないと仮定しています！
0(n^2)で書いたコードを示していただくことはできますでしょうか？
これが通じないということは「動的計画法を用いて O(n^2) で実装できた」というのは嘘ですね。
実装できたのではなく0(n^2)のアルゴリズムしか思いつかないと言うことです。
初めての質問だったので説明不足で申し訳ありません。
1.Sの先頭から順にT内の文字と同じになるかチェックする（O(n^2) Tの文字数は最大nであるため)
2.T内の全ての文字を含む連続部分文字列のうち、最小となるものを出力する(O(n)?)
S の長さが定数でないなら O(n) にはなりません。
nは入力Sの文字数（誤ってTと書いていました）なのですが、この場合、nは定数とは考えられないでしょうか？
初学者のため、基本的で拙い質問をしてしまいすみません。
n が定数なら O(1) になります。
回答3件
0
文字列Sの長さはnにしよう
文字列Tの長さはmにしよう
文字列Tが順序なければ
線形探索しないといけないので、一文字がTの中に存在するかを探せばO(m)で
文字列Sをどうしても一回遍歴しないといけないので、O(m)でO(n)回探す
そうすればO(n*m)となります
文字列Tが順序にすれば
二分探索ができるので、一文字ごとO(log(m))で
文字列Sをどうしても一回遍歴しないといけないので、O(log(m))でO(n)回探す
そうすればO(n*log(m))となります
文字列Tが順序かないか構わない
文字列Tにそのまま探索ではなく、前処理でハッシュセットに転じる
（例えば文字列TをASCIIに限られているのなら、bool[128]に転じるのも含めて）
前処理は文字列Tを一回遍歴するので、O(m)です
ハッシュセットに一文字を探すにはO(1)です（均しですけど）
文字列Sをどうしても一回遍歴しないといけないので、O(1)でO(n)回探す
そうすればO(m+n*1)、つまりO(m+n)となります
入力を利用しようとしたら、必ず一回遍歴すべきなので、O(m+n)は限界です。
投稿2020/06/24 12:00
総合スコア463
0
Tの取りうる組み合わせをすべて配列にして，その配列に対する最小連続部分文字列を探して一番小さいのを調べればO(n)になりそう？
Tが大きいと大変そうだけど…
投稿2020/06/24 11:23
総合スコア295
0
ベストアンサー
1.Sの先頭から順にT内の文字と同じになるかチェックする（O(n^2) Tの文字数は最大nであるため)
Tの範囲が充分狭いのなら、事前にTにどのような文字が存在するか配列に開いておけば、1文字のチェックは定数時間で済ませられるかと思います。
投稿2020/06/24 10:29
総合スコア145183
あなたの回答
tips
プレビュー
