文字列 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);
}
}
//編集:ウィキペディアの記事を正しく読むだけで問題は解決しました。