文字列の出現回数を別の文字列に返すプログラムを作成するにはどうすればよいですか？

Question

私はプログラミングが初めてです。私はjavaを使用しています。今、私はjavaを教えるウェブサイトでは解決できない課題があります。

これが割り当て

は別の文字列内の文字列の出現回数を返すプログラムを書いています。

例：

入力：

最初の文字列：

2番目の文字列：

：彼らはそれを 出力を愛しているから学生が工学部に一生懸命に働いています

注：ネストループのみを使用してください。 indexOfや部分文字列などのメソッドは使用しないでください。

私はenter image description hereは出現数を計算するコードに達したが、それは例：

入力繰り返し文字の場合には

を失敗しました：

最初の文字列：oooの

2番目の文字列： wooooooooooooooooooooow

出力：21

これは7回だけ繰り返されているためです。

Answer 1

この質問は、z-functionを線形時間で単純に解決できます。

int NumberOfcopies(String t, String h){ 
    // t = the first string i.e "ooo" 
    // h = the second string i.e "wooooooooooooooooooooow" 

    String s = t + "$" + h; // adding a sentinel character in between 
    int n = s.length(); // length of new string 
    int[] z = new int[n]; // z array 

    // Code ref : http://e-maxx-eng.github.io/string/z-function.html 
    int l = 0, r = 0; 
    for (int i = 1; i < n; i++){ 
     if (i <= r) 
      z[i] = Math.min(r - i + 1, z[i - 1]); 
     while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) 
      ++z[i]; 
     if (i + z[i] - 1 > r){ 
      l = i; 
      r = i + z[i] - 1; 
     } 
    } 

    //checking for all the occurance of string t in string h 
    int res = 0; 
    for (int i = t.length() + 1; i < n;){ 
     if (z[i] == t.length()){ 
      //A copy is found so skip next t.length chars 
      i += t.length(); 
      ++res; 
     } 
     else ++i; 
    } 
    System.out.println("Number of Occurance : " + res); 
    return res; 
} 

この文字列のZ機能は、長さの配列である i番目要素が位置Iをから始まる文字 の最大数に等しいNそのsの最初の の文字と一致します。

これは、別の文字列Hの文字列トンの出現数を見つけるために利用することができます。新しい文字列sを形成するために、文字列tとhを中間のsentinel文字で結合したとします（Sentinel文字はどちらの文字列にもない文字です）。

z関数を配列z[]で計算できるようにします。

ここで、センチネル文字の後の文字、つまり文字列hの文字から検索を開始できるようにします。文字列hのi番目の文字（i番目の文字が文字列sに属するような文字）の場合、z[i]が文字列tの長さ（パターン）と等しい場合は、i番目の文字から始まり、t.length()の文字は最初にt.length()文字列sの文字列は、文字列tが等しいものです。

例：
T = AB
H = aaabaab

S = ABの$ aaabaab
Z = 0 0 0 1 1 2 0 1 2 0
I = 0 1 2 3 4 5 6 7 8 9

i = 5私たちはz[i] == t.length()を見ることができます。これはコピーが見つかりました。オーバーラッピングソリューションを避けるため、今度はt.length()文字をスキップします。i = 7

これを続けると結果が得られます。