我已經實現了在字符串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);
}
}
//編輯:我解決了我的問題我只需要正確閱讀維基百科文章。
那你試試? –
我想計算stringB中stringA的出現次數。例如,我有stringA =「ST」和stringB =「XZSTZXZXSTST」。我想要的是它計算在這種情況下爲3的「ST」的發生。 //編輯:我現在正在做的是搜索與KMP的第一次出現,並從該位置切割字符串與子字符串。 – user1058712
請縮進您的代碼。你會得到更多的幫助。 –