1

文字列 B 内の文字列 A を検索するための Knuth-Morris-Pratt アルゴリズムを実装しました。文字列が見つかった場合は、文字列の最初の位置を返します。しかし今、文字列 B 内の文字列 A の合計出現回数を数えたいと思います。

簡単な方法を試してみましたが、うまくいきましたが、大きな文字列では時間がかかるため、効率的ではないようです。

誰でもこの問題を解決できますか? KMPでもっと効率的な方法が欲しい。

これは私のテストです。

public static int searchStringWithKnuthMorrisPratt(String s, String t)
    {
    int m=s.length();
    int n=t.length();
    int i=0,j=0,
            k=0
                    ;
    int[] B=new int[m+1];
    B[0]=-1; B[1]=0;
    for (int l=2; l<=m; l++)
    {
    while ((k>=0) && !(s.charAt(k)==s.charAt(l-1))) k=B[k];
    B[l]=++k;
    }
    while (i<=(n-m))
    {
    while ((j<m) && (s.charAt(j)==t.charAt(i+j))) j++;
    if (j==m) return(i);
    i=i+j-B[j];
    j=Math.max(0, B[j]);
}
    return(-1);
}

public static void main(String[] args)
{
            String stringA = "ST";
            String stringB = "XSTXXXSTX";
            int count = 0;
            int result = searchStringWithKnuthMorrisPratt(stringA,stringB);
            while(result>-1) {
            count++
            stringB = stringB.substring(result+2);
            result= searchStringWithKnuthMorrisPratt(stringA,stringB);

              }
}

//編集:ウィキペディアの記事を正しく読むだけで問題は解決しました。

4

2 に答える 2

0

あなたは「大きな文字列では時間がかかる」と述べています。

Boyer Moore Horspool アルゴリズムを使用することをお勧めします。パターンの長さが長くなるほど速くなります。また、入力テキストを部分文字列で切り取ると、パフォーマンスが低下します。代わりに、検索の開始点を指定するパラメーターを追加できます。

于 2013-07-02T01:52:44.880 に答える
0

「KMP with Continuation」の C++ 実装はこちらと以下にあります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long uint32;
typedef long int32;
typedef unsigned long long uint64;
typedef long long int64;

/**
* Restartable KMP Search, use as follows:
*
* uint32 h_ix = 0, n_ix = 0;
* vector<int32> kmptab = kmp_table(needle);
* for (;;) {
*   h_ix = kmp_search(haystack, needle, kmptab, h_ix, n_ix);
*   if (h_ix == haystack.size()) break;
*
*   // found one
*   n_ix = kmptab.back();
*   h_ix += needle.size() - n_ix;
* }
*
* If found, returns index.  If not, returns size of haystack (invalid index).
*/
vector<int32> kmp_table(vector<uint32> w);
uint32 kmp_search(const vector<uint32>& haystack, const vector<uint32>& needle, const vector<int32>& kmptab, uint32 h_ix = 0, uint32 n_ix = 0) {

    while (h_ix + n_ix < haystack.size()) {
        if (needle[n_ix] == haystack[h_ix + n_ix]) {
            if (n_ix == needle.size() - 1) return h_ix;
            n_ix++;
        }
        else {
            h_ix += n_ix - kmptab[n_ix];
            if (kmptab[n_ix] >= 0) {
                n_ix = kmptab[n_ix];
            }
            else {
                n_ix = 0;
            }
        }
    }

    /**
    * Not found, return string end.
    */
    return haystack.size();
}
vector<int32> kmp_table(vector<uint32> w) {

    /**
    * Makes for restartable search.
    * Optimization idea: make input const reference, generate final value below explicitly.
    */
    w.push_back(0);

    uint32 pos = 2, cand = 0;

    vector<int32> t(max(static_cast<int32>(2), static_cast<int32>(w.size())));
    t[0] = -1;
    t[1] = 0;
    while (pos < w.size()) {
        if (w[pos - 1] == w[cand]) {
            cand++;
            t[pos] = cand;
            pos++;
        }
        else if (cand > 0) {
            cand = t[cand];
        }
        else {
            t[pos] = 0;
            pos++;
        }
    }
    return t;
}
于 2014-12-04T16:09:48.417 に答える