CODEWITHSUNDEEP
javarecursionword-frequency
user8636215
user8636215

Reputation:

Counting the number of occurences of a string inside a string

Here is my attempt at this method.

Count the number of co-occurrances of a non-empty sub-string sub within the string str E.g.

numOccurances("dogmonkeydog","dog") will return 2

numOccurances("dogmonkeydog","mon") will return 1

numOccurances("dogmonkeydog","cow") will return 0

public static int numOccurrences(String str, String sub) {
    int result = 0;
    int pos = str.indexOf(sub);
    if (pos == -1){
        return result;
    }
    if (sub.length() > str.length()){
        return result;
    }
    if ((str.substring(0, sub.length())).equals(sub)){
        result++;
        String st = str.substring(pos);
        return result + numOccurrences(st, sub); //Line 87
    }
    else{
        String st = str.substring(sub.length());
        return result + numOccurrences(st, sub);
    }
}

I get this failure for all tests where the result > 0

java.lang.StackOverflowError
    at java.lang.String.indexOf(String.java:1718)
    at java.lang.String.indexOf(String.java:1698)
    at eecs2030.lab6.RecursiveTasks.numOccurrences(RecursiveTasks.java:77)
    at eecs2030.lab6.RecursiveTasks.numOccurrences(RecursiveTasks.java:87)

I'm unsure as to why my code never reaches its base case, any insight would be much appreciated!

Upvotes: 0

Views: 202

Answers (4)

Praveen
Praveen

Reputation: 1871

1 : public static int numOccurrences(String str, String sub) {
2 :    int result = 0;
3 :    int pos = str.indexOf(sub);
4 :    if (pos == -1){
5 :        return result;
6 :    }
7 :    if (sub.length() > str.length()){
8 :        return result;
9 :    }
10:    if ((str.substring(0, sub.length())).equals(sub)){
11:        result++;
12:        String st = str.substring(pos);
13:        return result + numOccurrences(st, sub); 
14:    }
15:    else{
16:        String st = str.substring(sub.length());
17:        return result + numOccurrences(st, sub);
18:    }
19:}

Line 10 - You are not extracting the substring of the given sub string parameter in the actual string str.
Line 12 - You are almost there in discarding the current substring for the next call but you are including the string too. Example: monstrfri -> with substring str will result in strfri rather than fri

If you prefer to change your logic, you can get this through a simple while loop pos is index of substring

counter is 0
while pos!=-1
    increment the counter
    trim the current substring found
    extract the next position
    and continue while

Upvotes: 1

Namrata Shukla
Namrata Shukla

Reputation: 157

The third if condition in your method is not needed.

 if ((str.substring(0, sub.length())).equals(sub))

you can simply define the third case as

 if(pos>=0)
  {
  result++;
  String newstr = str.substring(pos + sub.length());
  return numOccurrences(newstr,sub);
  }

since, if the substring is find ,the pos variable will be initialised by starting index of substring, you can increment result here.

then recursively call numOccurences() method on the rest of the string. and also declare variable result outside of the method.

 import java.util.Scanner;
 class SubString
 {
 String user,subUser;
 Scanner sc=new Scanner(System.in);
 int num;
 static  int result = 0;
 int numOccurrences(String str, String sub) {

  int pos = str.indexOf(sub);
  if (pos == -1){
    return result;
 }
 if (sub.length() > str.length()){
    return result;
  }
  else if(pos >= 0)
  {
   result++;
   String newstr = str.substring(pos + sub.length());
   return numOccurrences(newstr,sub);
   }
 return result;

 }

//constructor
 SubString()
 {
   try{
   System.out.println("Enter string :");
   user=sc.nextLine();
   System.out.println("Enter the substring: ");
   subUser=sc.nextLine();
   num = numOccurrences(user,subUser);
   System.out.println(num);
  }
   catch(Exception e)
   {
    System.out.println(e);
   } 

 }
 public static void main(String...a)
{
 new SubString();
 }
 }

`

Upvotes: 1

Saranya Subramanian
Saranya Subramanian

Reputation: 461

      public static int findOcc(String str,String sub){
        int count =0;
        int occurence = 0;
        char strArray [] = str.toCharArray();
        char subArray [] = sub.toCharArray();
        for(int i=0;i<strArray.length;i++){
            if(strArray[i]==subArray[0]){
              for(int j=0,k=i;j<subArray.length && k < strArray.length 
              ;j++,k++){
                        if(strArray[k]==subArray[j]){
                          count++;
                        }
                       }
                       if(count == subArray.length){
                          occurence++;
                 }
                 count =0;
              }
         }
      return occurence;
    }

Upvotes: 0

anacron
anacron

Reputation: 6721

This seems like an school assignment. So, I'll not give you the answer directly.

In the following snippet,

result++;
String st = str.substring(pos);
return result + numOccurrences(st, sub); //Line 87

the place where you are creating st is problematic. If str begins with the value contained in sub, then str will be equal to st. So, the call to numOccurrences will be same as your original call and so your recursion will not terminate.

Analyze what needs to be passed to str.substring in the above snippet.

Hope this helps!

Upvotes: 0

Related Questions