1

固定部分文字列検索の場合、O(n) ランタイムと O(1) 作業スペースを備えた既知のアルゴリズムが正確に 2 つあります: SMOA と Two-Way ( http://www-igm.univ-mlv.fr/~lecroq/を参照)文字列/ )。どちらも、アルファベットに順序付けを行うか、課すことに依存しています。

固定された部分文字列を検索する代わりに、ブラケット式で表現された一連の部分文字列のいずれかを検索できるようにしたいとします。

 [abc]d

"ad"、"bd"、または "cd" に一致します。アルファベットが有限であると仮定すると、ブラケットの長さは制限されるため、時間またはスペースの要件における「ブラケットの長さ」という形式の項は O(1) です。

O(n) 時間 (n検索対象の文字列の長さ、つまり「干し草の山」) と O(1) の作業スペースで検索を実行する方法はありますか?

解決策が何らかの方法でブラケット セットをアルファベット順で順序付けすることを含まない限り、この問題に対する解決策は、順序付け要件なしで O(n)/O(1) の固定部分文字列検索問題に対する新しい解決策を提供するため、非常にありそうにないようです。存在する。

4

1 に答える 1

0

私は何かが欠けているに違いない。リンクされたページからのブルート フォース メソッドは O(n) です。探しているものを簡単に書くことができるようです：

1.  Pattern is P with index p indicating which element of the pattern we are on.
2.  String is S with index s indicating which element of the string we are on.
3.  if S[s] matches P[p], increment both indicies and repeat until you complete the Pattern.
4.  If S[s] doesn't match P[p], set p=0 and increment p.

それは O(n) であり、要件を満たします。

于 2012-08-27T18:28:20.210 に答える