java 字符串中的子字符串数

Count of substrings within string

提问by Mark

My program should do the following:

我的程序应该执行以下操作：

1. User enters a string: University of the Cordilleras
2. User enters the substring: er
3. Program outputs the substring-count: 2 (University of the Cordilleras)

1. 用户输入一个字符串：科迪勒拉斯大学
2. 用户输入子字符串：er
3. 程序的输出子数：2（大学ER的Cordill的减到ER为）

I should not use .str, but create my own method.

我不应该使用 .str，而是创建我自己的方法。

回答by aioobe

The naive approach (checking for substring at each possible index) runs in O(nk)where nis the length of the string and kis the length of the substring. This could be implemented with a for-loop, and something like haystack.substring(i).startsWith(needle).

天真的方法（在每个可能的索引处检查子字符串）以O(nk) 运行，其中n是字符串的长度，k是子字符串的长度。这可以用 for 循环来实现，比如haystack.substring(i).startsWith(needle).

More efficient algorithms exist though. You may want to have a look at the Knuth-Morris-Pratt algorithm, or the Aho-Corasick algorithm. As opposed to the naive approach, both of these algorithms behave well also on input like "look for the substring of 100 'X' in a string of 10000 'X's.

但是，存在更有效的算法。您可能想查看Knuth-Morris-Pratt 算法或Aho-Corasick 算法。与天真的方法相反，这两种算法在输入时也表现良好，例如“在 10000 个 'X' 的字符串中查找 100 个 'X' 的子字符串。

回答by hrzafer

Just replace the first occurrence and count until there is none.

只需替换第一次出现并计数，直到没有出现。

int count = 0;
while (str.indexOf(subStr)>-1){
    str = str.replaceFirst(subStr, "");
    count++;
}
return count ;

回答by Nagamani R.R

Here is my Code....

这是我的代码....

 import java.util.Scanner;
public class occurrenceOf_Substring {

public static void main(String[] args) {


    Scanner input=new Scanner(System.in);

    System.out.println(" Enter a string");

    String str=input.nextLine();

    System.out.println(" Enter a substring");       

    String substring=input.nextLine();

    int l=substring.length();



        int count=0;      
        int index=str.indexOf(substring); // To find first occurrence


        while(index<str.length() && index != -1) 
        {
            index=str.indexOf(substring,index+l);/// to find next occurrences 

            count=count+1;
        }


    System.out.println("substrin count is    "+count);
} }

回答by Nagamani R.R

Algorithm:

算法：

step 1: convert mainstring to character array

步骤 1：将主字符串转换为字符数组

step 2: convert substring to character array

步骤 2：将子字符串转换为字符数组

step 3: compare two arrays character by character

第 3 步：逐个字符比较两个数组

step 4: If at least one of the character in the substring array not matches with mainstring character array starts from first character of the substring, but keep moving in the main string

步骤4：如果子串数组中至少有一个字符与主串字符数组不匹配，则从子串的第一个字符开始，但在主串中继续移动

step 5: If all the character of substring gets matched increment the count and start from first position of the substring again that's it.

第 5 步：如果子字符串的所有字符都匹配，则增加计数并再次从子字符串的第一个位置开始，就是这样。

  import java.io.*;
  import java.util.Scanner;
  public class SubStringCount {

public static void main(String[] args) throws IOException {


    Scanner input=new Scanner(System.in);
    System.out.println("Enter you Main string:");
    String mainstring=input.nextLine();
    System.out.println("Enter the substring");
    String substring=input.nextLine();
    int i=0;int j=0;
    char[] str=mainstring.toCharArray(); // converting main string to character array
    char[] sub=substring.toCharArray(); // converting substring to character array
    int count=0;
    while(i<str.length)
    {
        if(str[i]==sub[j])
        {
                  j++;
        }
        else
        {
            j=0; 
        }
        if(j==sub.length)
        {
            j=0;
            count++;
        }
        i++;

    }

回答by doctorram

In one line:

在一行中：

int count = (str.length() - str.replace(subStr, "").length()) / subStr.length();

回答by Andreas Dolk

1. A String is a sequence of charvalues (like an array)
2. Loop through this sequence and for every char (except the last in your example):
   1. test, if thischar is equal to the first char of your pattern and if the nextchar is equal the second char of your pattern (adapt, if you have patterns of a different size)
   2. If the test result is true, increment your counter.

1. 字符串是char值的序列（如数组）
2. 循环遍历此序列和每个字符（示例中的最后一个除外）：
   1. 测试，如果这个字符等于你的模式的第一个字符，并且下一个字符等于你的模式的第二个字符（适应，如果你有不同大小的模式）
   2. 如果测试结果是true，请增加您的计数器。

This is the basic algorithm. If you have this up and running, think about special cases, like the source String is empty or shorter then the pattern.

这是基本算法。如果您启动并运行了它，请考虑特殊情况，例如源字符串为空或比模式短。

回答by jsteltze

Another one-liner might be: use split("sep", -1), then you have the array length (-1).

另一个单行代码可能是：使用split("sep", -1)，那么您就有数组长度 (-1)。

Example:

例子：

String input    = "@human@mail@@com@";
String search   = "@";
int occurrences = input.split(search, -1).length - 1;

Explanation:splitsplits the input string by the given separator (regex). So it returns an array with the substrings between the separator. The second parameter -1tells split to not limit the array length by any means. If split is used with the default limit (0) trailing empty strings will be discarded (-> wrong result if the string to search is at the end). So to finally get the number of occurrences of the search string, the array length has to be reduced by 1.

说明：split通过给定的分隔符（正则表达式）分割输入字符串。所以它返回一个包含分隔符之间的子字符串的数组。第二个参数-1告诉 split 不以任何方式限制数组长度。如果 split 与默认限制 (0) 一起使用，尾随的空字符串将被丢弃（-> 如果要搜索的字符串在末尾，则会出现错误的结果）。所以为了最终得到搜索字符串的出现次数，数组长度必须减1。