問題タブ [boyer-moore]

宿題の質問があります：

a の b と c で構成される文字列を入力として取り、各部分文字列 abc の末尾に 1 を含み、他のすべての位置に 0 を含む文字列を出力する Moore マシンを構築します。例: 入力 aabcb は出力 000010 を生成します

構築してみましたが、行き止まりになってしまいました。これが私の試みです：

ご覧のとおり、文字列 cccb を作成できず、'abc' は 0 を出力できます。この単純な問題を複雑にしすぎたように感じます。

編集：休憩を取って、それをやり直しました。誰かが私に別のことを言わない限り、これは正しいと思います：

Boyer-Moore 文字列検索アルゴリズムの wikiリンクでは、Boyer-Moore の最悪の場合の複雑さが

1. O(m+n)パターンがテキストに現れない場合
2. パターンがテキストに出現する場合はO(mn)

しかし、String Search Algorithm wikiでは、Boyer-Moore の最悪の場合の複雑さはO(n)であると述べられています。この格差はなぜですか？

ここでも最悪の場合 O(mn) と記載されています。

では、Boyer-Moore アルゴリズムの正しい実行時間の複雑さはどれくらいですか?

Boyer-Moore 文字列マッチング アルゴリズムを実装したいのですが、並列アプローチを使用してそのアルゴリズムを実装したいと考えています。アルゴリズムを並列実行した場合と逐次実行した場合の実行時間の違いを示したいと思います。

このために、ノードのクラスターでコードを実行することを考えています。現時点では、Hadoop を使用して AWS (Amazon Web Services) - EMR (Elastic Map Reduce) を使用する予定ですが、問題は、AWS が非常に使いにくいことです。

Java コードを複数のクラスターで並行して実行するのに役立つ、AWS のような他のサービスはありますか? コードを並行して実行する方法に関する提案をお待ちしています。

Sedgewick の Boyer Moore 部分文字列検索ソリューションを使用する必要がある Java の割り当てがあります: http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

単語の最初の出現が見つかったときに停止し、見つかった場所を返します。単語を数えるために、検索方法を次のように変更しました。

if skip ステートメントを変更して、カウンター「カウント」を実行し、最後にそれを返します。何が起こるかというと、パターンといくつかのテキストを手動でフィードすると、うまくカウントされるようです:

パターン: テスト テキスト: 「このテストはテスト テスト testtest です」 結果: 5

ただし、約70kワードのテキストのtxtファイルと部分文字列検索を読み取る必要があります。

そのため、単語を検索すると、Mac テキスト エディターでファイル自体を CMD+F したときよりもずっと少ない数値が常に得られます。何がうまくいかないのですか？

この Boyer Moore Algorithm を C# コードで記述しましたが、テキストとパターンを入力しても解決策が得られません。実装しなければならないアルゴリズムが与えられました。コードですべてのロジックを実行しましたが、解決策は得られませんでした。