2013-07-02 53 views
1

我已經實現了在字符串B中搜索字符串A的Knuth-Morris-Pratt算法。 如果找到字符串if返回字符串的第一個位置,則返回-1。 但是現在我想要計算字符串B中字符串A的總髮生次數。KMP計數字符串發生

我試過一種簡單的方法,它工作正常,但這看起來並不高效,因爲它需要大量時間處理大字符串。

任何人都可以幫我解決這個問題嗎?我想要一個更有效的方式與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); 

       } 
} 

//編輯:我解決了我的問題我只需要正確閱讀維基百科文章。

+1

那你試試? –

+0

我想計算stringB中stringA的出現次數。例如,我有stringA =「ST」和stringB =「XZSTZXZXSTST」。我想要的是它計算在這種情況下爲3的「ST」的發生。 //編輯:我現在正在做的是搜索與KMP的第一次出現,並從該位置切割字符串與子字符串。 – user1058712

+0

請縮進您的代碼。你會得到更多的幫助。 –

回答

0

您提到「需要大量時間處理大字符串」。

我建議你使用Boyer Moore Horspool算法。隨着模式長度增加,它得到更快。另外,用子串切割輸入文本會給性能帶來不好的影響。相反,您可以添加一個參數來指定搜索的起點。

0

A 「KMP與延續」 C++實現here,以下:

#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; 
}