CODEWITHSUNDEEP
javastringstring-matching
bobcom
bobcom

Reputation:

Find the Number of Occurrences of a Substring in a String

Why is the following algorithm not halting for me?

In the code below, str is the string I am searching in, and findStr is the string occurrences of which I'm trying to find.

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;
    
while (lastIndex != -1) {
    lastIndex = str.indexOf(findStr,lastIndex);
    
    if( lastIndex != -1)
        count++;
           
    lastIndex += findStr.length();
}

System.out.println(count);

Upvotes: 173

Views: 466583

Answers (27)

Mark Andreev
Mark Andreev

Reputation: 31

The best solution to this problem you can find in org.springframework.util.StringUtils.countOccurrencesOf(string, substring):

// IndexOfWithJumpSubstringCounterImpl (countOccurrencesOf after refactoring)
public static int count(String string, String substring) {
    if (string == null || string.length() == 0 
        || substring == null || substring.length() == 0) {
        return 0;
    }

    int count = 0;
    int idx;
    for(int pos = 0; (idx = string.indexOf(substring, pos)) != -1; pos = idx + substring.length()) {
        ++count;
    }

    return count;
}

There is performance comparison based on JMH (full report: https://medium.com/p/d924cf933fc3):

(impl)                                Mode  Cnt      Score     Error   Units
IndexOfWithJumpSubstringCounterImpl  thrpt   10  86171.752 ± 225.064  ops/ms
IndexOfSubstringCounterImpl          thrpt   10  77560.418 ± 154.745  ops/ms
ReplaceBasedSubstringCounterImpl     thrpt   10  29758.761 ±  35.899  ops/ms
RegExSubstringCounterImpl            thrpt   10   5121.197 ±  10.030  ops/ms

Upvotes: 0

Alexander Ivanchenko
Alexander Ivanchenko

Reputation: 28968

Matcher.results()

You can find the number of occurrences of a substring in a string using Java 9 method Matcher.results() with a single line of code.

It produces a Stream of MatchResult objects which correspond to captured substrings, and the only thing needed is to apply Stream.count() to obtain the number of elements in the stream.

public static long countOccurrences(String source, String find) {
    
    return Pattern.compile(find) // Pattern
        .matcher(source) // Mather
        .results()       // Stream<MatchResults>
        .count();
}

main()

public static void main(String[] args) {
    System.out.println(countOccurrences("helloslkhellodjladfjhello", "hello"));
}

Output:

3

Upvotes: 3

mjs
mjs

Reputation: 22347

Here it is, wrapped up in a nice and reusable method:

public static int count(String text, String find) {
        int index = 0, count = 0, length = find.length();
        while( (index = text.indexOf(find, index)) != -1 ) {                
                index += length; count++;
        }
        return count;
}

Upvotes: 14

Shahid Sarwar
Shahid Sarwar

Reputation: 1209

I was asked this question in an interview just now and I went completely blank. (Like always, I told myself that the moment the interview ends ill get the solution) which I did, 5 mins after the call ended :(

    int subCounter=0;
    int count =0;
    for(int i=0; i<str.length(); i++) {
        if((subCounter==0 && "a".equals(str.substring(i,i+1))) 
                || (subCounter==1 && "b".equals(str.substring(i,i+1)))
                || (subCounter==2 && "c".equals(str.substring(i,i+1)))) {
            ++subCounter;
        }
        if(subCounter==3) {
            count = count+1;
            subCounter=0;
        }
    }
    System.out.println(count);

Upvotes: 0

ucMax
ucMax

Reputation: 5428

🍑 Just a little more peachy answer

    public int countOccurrences(String str, String sub) {
        if (str == null || str.length() == 0 || sub == null || sub.length() == 0) return 0;
        int count = 0;
        int i = 0;
        while ((i = str.indexOf(sub, i)) != -1) {
            count++;
            i += sub.length();
        }
        return count;
    }

Upvotes: 0

Anubhav Singh
Anubhav Singh

Reputation: 8699

This solution prints the total number of occurrence of a given substring throughout the string, also includes the cases where overlapping matches do exist.

class SubstringMatch{
    public static void main(String []args){
        //String str = "aaaaabaabdcaa";
        //String sub = "aa";
        //String str = "caaab";
        //String sub = "aa";
        String str="abababababaabb";
        String sub = "bab";

        int n = str.length();
        int m = sub.length();

        // index=-1 in case of no match, otherwise >=0(first match position)
        int index=str.indexOf(sub), i=index+1, count=(index>=0)?1:0;
        System.out.println(i+" "+index+" "+count);

        // i will traverse up to only (m-n) position
        while(index!=-1 && i<=(n-m)){   
            index=str.substring(i, n).indexOf(sub);
            count=(index>=0)?count+1:count;
            i=i+index+1;  
            System.out.println(i+" "+index);
        }
        System.out.println("count: "+count);
    }
}

Upvotes: 1

duggu
duggu

Reputation: 38409

This below method show how many time substring repeat on ur whole string. Hope use full to you:-

    String searchPattern="aaa"; // search string
    String str="aaaaaababaaaaaa"; // whole string
    int searchLength = searchPattern.length(); 
    int totalLength = str.length(); 
    int k = 0;
    for (int i = 0; i < totalLength - searchLength + 1; i++) {
        String subStr = str.substring(i, searchLength + i);
        if (subStr.equals(searchPattern)) {
           k++;
        }

    }

Upvotes: 1

kmecpp
kmecpp

Reputation: 2479

I'm very surprised no one has mentioned this one liner. It's simple, concise and performs slightly better than str.split(target, -1).length-1

public static int count(String str, String target) {
    return (str.length() - str.replace(target, "").length()) / target.length();
}

Upvotes: 60

Nikolai Nechai
Nikolai Nechai

Reputation: 131

public static int getCountSubString(String str , String sub){
int n = 0, m = 0, counter = 0, counterSub = 0;
while(n < str.length()){
  counter = 0;
  m = 0;
  while(m < sub.length() && str.charAt(n) == sub.charAt(m)){
    counter++;
    m++; n++;
  }
  if (counter == sub.length()){
    counterSub++;
    continue;
  }
  else if(counter > 0){
    continue;
  }
  n++;
}

return  counterSub;

}

Upvotes: 0

Maksym Ovsianikov
Maksym Ovsianikov

Reputation: 509

public int countOfOccurrences(String str, String subStr) {
  return (str.length() - str.replaceAll(Pattern.quote(subStr), "").length()) / subStr.length();
}

Upvotes: 8

dfa
dfa

Reputation: 116314

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while((lastIndex = str.indexOf(findStr, lastIndex)) != -1) {
     count++;
     lastIndex += findStr.length() - 1;
}
System.out.println(count);

at the end of the loop count is 3; hope it helps

Upvotes: 8

Venzentx
Venzentx

Reputation: 487

Here is the advanced version for counting how many times the token occurred in a user entered string:

public class StringIndexOf {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter a sentence please: \n");
        String string = scanner.nextLine();

        int atIndex = 0;
        int count = 0;

        while (atIndex != -1)
        {
            atIndex = string.indexOf("hello", atIndex);

            if(atIndex != -1)
            {
                count++;
                atIndex += 5;
            }
        }

        System.out.println(count);
    }

}

Upvotes: 1

Bhushan Bhangale
Bhushan Bhangale

Reputation: 10987

public int indexOf(int ch,
                   int fromIndex)

Returns the index within this string of the first occurrence of the specified character, starting the search at the specified index.

So your lastindex value is always 0 and it always finds hello in the string.

Upvotes: 2

Stanislav Kniazev
Stanislav Kniazev

Reputation: 5488

Increment lastIndex whenever you look for next occurrence.

Otherwise it's always finding the first substring (at position 0).

Upvotes: 3

Victor
Victor

Reputation: 781

You can number of occurrences using inbuilt library function:

import org.springframework.util.StringUtils;
StringUtils.countOccurrencesOf(result, "R-")

Upvotes: 6

Olivier
Olivier

Reputation: 3495

Your lastIndex += findStr.length(); was placed outside the brackets, causing an infinite loop (when no occurence was found, lastIndex was always to findStr.length()).

Here is the fixed version :

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while (lastIndex != -1) {

    lastIndex = str.indexOf(findStr, lastIndex);

    if (lastIndex != -1) {
        count++;
        lastIndex += findStr.length();
    }
}
System.out.println(count);

Upvotes: 139

Jean
Jean

Reputation: 21595

Do you really have to handle the matching yourself ? Especially if all you need is the number of occurences, regular expressions are tidier :

String str = "helloslkhellodjladfjhello";
Pattern p = Pattern.compile("hello");
Matcher m = p.matcher(str);
int count = 0;
while (m.find()){
    count +=1;
}
System.out.println(count);

Upvotes: 83

sjkm
sjkm

Reputation: 3937

Based on the existing answer(s) I'd like to add a "shorter" version without the if:

String str = "helloslkhellodjladfjhello";
String findStr = "hello";

int count = 0, lastIndex = 0;
while((lastIndex = str.indexOf(findStr, lastIndex)) != -1) {
    lastIndex += findStr.length() - 1;
    count++;
}

System.out.println(count); // output: 3

Upvotes: 1

benkc
benkc

Reputation: 3382

A lot of the given answers fail on one or more of:

  • Patterns of arbitrary length
  • Overlapping matches (such as counting "232" in "23232" or "aa" in "aaa")
  • Regular expression meta-characters

Here's what I wrote:

static int countMatches(Pattern pattern, String string)
{
    Matcher matcher = pattern.matcher(string);

    int count = 0;
    int pos = 0;
    while (matcher.find(pos))
    {
        count++;
        pos = matcher.start() + 1;
    }

    return count;
}

Example call:

Pattern pattern = Pattern.compile("232");
int count = countMatches(pattern, "23232"); // Returns 2

If you want a non-regular-expression search, just compile your pattern appropriately with the LITERAL flag:

Pattern pattern = Pattern.compile("1+1", Pattern.LITERAL);
int count = countMatches(pattern, "1+1+1"); // Returns 2

Upvotes: 7

A_M
A_M

Reputation: 7851

How about using StringUtils.countMatches from Apache Commons Lang?

String str = "helloslkhellodjladfjhello";
String findStr = "hello";

System.out.println(StringUtils.countMatches(str, findStr));

That outputs:

3

Upvotes: 245

codebreach
codebreach

Reputation: 2220

The last line was creating a problem. lastIndex would never be at -1, so there would be an infinite loop. This can be fixed by moving the last line of code into the if block.

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while(lastIndex != -1){

    lastIndex = str.indexOf(findStr,lastIndex);

    if(lastIndex != -1){
        count ++;
        lastIndex += findStr.length();
    }
}
System.out.println(count);

Upvotes: 92

Arik
Arik

Reputation: 6501

As @Mr_and_Mrs_D suggested:

String haystack = "hellolovelyworld";
String needle = "lo";
return haystack.split(Pattern.quote(needle), -1).length - 1;

Upvotes: 1

Rhino
Rhino

Reputation: 101

If you need the index of each substring within the original string, you can do something with indexOf like this:

 private static List<Integer> getAllIndexesOfSubstringInString(String fullString, String substring) {
    int pointIndex = 0;
    List<Integer> allOccurences = new ArrayList<Integer>();
    while(fullPdfText.indexOf(substring,pointIndex) >= 0){
       allOccurences.add(fullPdfText.indexOf(substring, pointIndex));
       pointIndex = fullPdfText.indexOf(substring, pointIndex) + substring.length();
    }
    return allOccurences;
}

Upvotes: 0

Arun Kumar Mudraboyina
Arun Kumar Mudraboyina

Reputation: 779

here is the other solution without using regexp/patterns/matchers or even not using StringUtils.

String str = "helloslkhellodjladfjhelloarunkumarhelloasdhelloaruhelloasrhello";
        String findStr = "hello";
        int count =0;
        int findStrLength = findStr.length();
        for(int i=0;i<str.length();i++){
            if(findStr.startsWith(Character.toString(str.charAt(i)))){
                if(str.substring(i).length() >= findStrLength){
                    if(str.substring(i, i+findStrLength).equals(findStr)){
                        count++;
                    }
                }
            }
        }
        System.out.println(count);

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533492

A shorter version. ;)

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
System.out.println(str.split(findStr, -1).length-1);

Upvotes: 115

Xander
Xander

Reputation: 5587

Try this one. It replaces all the matches with a -.

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int numberOfMatches = 0;
while (str.contains(findStr)){
    str = str.replaceFirst(findStr, "-");
    numberOfMatches++;
}

And if you don't want to destroy your str you can create a new string with the same content:

String str = "helloslkhellodjladfjhello";
String strDestroy = str;
String findStr = "hello";
int numberOfMatches = 0;
while (strDestroy.contains(findStr)){
    strDestroy = strDestroy.replaceFirst(findStr, "-");
    numberOfMatches++;
}

After executing this block these will be your values:

str = "helloslkhellodjladfjhello"
strDestroy = "-slk-djladfj-"
findStr = "hello"
numberOfMatches = 3

Upvotes: 1

Thorsten Schleinzer
Thorsten Schleinzer

Reputation: 89

try adding lastIndex+=findStr.length() to the end of your loop, otherwise you will end up in an endless loop because once you found the substring, you are trying to find it again and again from the same last position.

Upvotes: 1

Related Questions