java如何编写一个程序，返回一个字符串在另一个字符串中出现的次数？

Question

所以我是编程新手。我正在使用java。现在我有一个作业，我无法在一个教授java的网站上解决

这是作业

编写一个程序，返回一个字符串在另一个字符串中出现的次数

例如

输入：

第一个字符串：

第二条线索：学生们在工程学院努力学习，因为他们热爱工程 输出：

三,

注意：您应该只使用嵌套循环。不要使用indexOf或substring之类的方法

Ienter image description here到达代码，计算出现的次数，但在重复字母的情况下失败

例如

输入：

第一个字符串：ooo

第二串：呜呜呜呜呜呜

产出：21

应该是7，因为ooo只重复了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;
}

The Z-function for this string is an array of length n where the i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s.

可以利用此函数来查找另一个字符串h中某个字符串t的出现次数。假设我们在字符串t和h之间加入一个前哨字符（前哨字符是两个字符串中都没有的字符），以形成一个新字符串s

让我们计算数组z[]中的z函数

现在让我们开始从前哨字符后的字符开始搜索，即字符串h的字符。对于字符串h中的第i个字符（因此第i个字符属于字符串s），如果z[i]等于字符串t的长度（模式），则意味着从第i个字符开始，t.length()字符与字符串s的第一个t.length()字符相同，这就是字符串t的值

示例：
t=ab
h=aaabaab

s=AB$AB
z=0 0 1 2 0 1 2 0
i=0123456789

对于i = 5我们可以看到z[i] == t.length()，这意味着我们找到了一个副本。现在为了防止重叠的解决方案，我们跳过t.length()字符，因此现在i = 7

继续此操作将得到结果