Количество подстрок в строке

Question

Моя программа должна сделать следующее:

1. Пользователь вводит строку: Университет Кордильер
2. Пользователь вводит подстроку: er
3. Программа выводит подстроку-count: 2 (Univ er sity of Cordill er as)

Я не должен использовать .str, но создаю свой собственный метод.

Answer 1

Просто замените первое вхождение и считайте, пока его не будет.

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

Answer 2

Наивный подход (проверка подстроки по каждому возможному индексу) выполняется в O (nk) , где n - длина строки, а k - длина подстроки. Это может быть реализовано с помощью цикла for и что-то вроде haystack.substring(i).startsWith(needle).

Однако существуют более эффективные алгоритмы. Возможно, вы захотите взглянуть на алгоритм Кнута-Морриса-Пратта или алгоритм Ахо-Корасика . В отличие от наивного подхода, оба этих алгоритма хорошо себя ведут и при вводе, например «ищите подстроку 100 X в строке 10000 X».

Answer 3

В одну строку:

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

Answer 4

Алгоритм:

шаг 1: преобразование главной строки в массив символов

шаг 2: преобразовать подстроку в массив символов

шаг 3: сравнить два массива символ за символом

шаг 4: Если хотя бы один из символов в массиве подстрок не совпадает с массивом символов основной строки, начинается с первого символа подстроки, но продолжает двигаться в основной строке

шаг 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++;

    }

Answer 5

Вот мой код ....

 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);
} }

Answer 6

1. Строка - это последовательность char значений (как массив)
2. Цикл по этой последовательности и для каждого символа (кроме последнего в вашем примере):
   1. проверьте, если этот символ равен первому символу вашего паттерна, а если следующий символ равен второму символу вашего паттерна (адаптируйте, если у вас есть шаблоны другого размера)
   2. Если результат теста равен true, увеличьте счетчик.

Это основной алгоритм.Если у вас есть это и работает, подумайте о специальных случаях, таких как исходная строка пуста или короче, чем шаблон.