Count of substrings within string

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-cou开发者_如何学编程nt: 2 (University of the Cordilleras)

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

---

The naive approach (checking for substring at each possible index) runs in O(nk) where n is the length of the string and k is the length of the substring. This could be implemented with a for-loop, and something like 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.

---

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 ;

---

1. A String is a sequence of char values (like an array)
2. Loop through this sequence and for every char (except the last in your example):
   1. test, if this char is equal to the first char of your pattern and if the next char 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.

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.

---

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

---

Algorithm:

step 1: convert mainstring to character array

step 2: convert substring to character array

step 3: compare two arrays character by character

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

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.

  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++;

    }

---

In one line:

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

---

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

Example:

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

Explanation: split splits the input string by the given separator (regex). So it returns an array with the substrings between the separator. The second parameter -1 tells 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.