CODEWITHSUNDEEP
java
Cyborg
Cyborg

Reputation: 11

Most efficient way to count number of overlapping occurrences

How do I count the number of overlapping occurences in a string efficiently?

For example, count('XLXXXLXX','XX') should return 3

Upvotes: 0

Views: 804

Answers (5)

Sunil Dabburi
Sunil Dabburi

Reputation: 1472

I would recommend String substring(<str>, index) approach as it's easier on the eyes.

If you want to try with more basic code to understand what's happening under hood, here is a character array approach.

private static int count(String givenStr, String overlappingStr) {

    char[] first = givenStr.toCharArray();
    char[] second = overlappingStr.toCharArray();

    int matchCount = 0;
    for (int i = 0; i < first.length; i++) {

        int count = 0;
        for (int j = 0, index = i; j < second.length && index < first.length; j++, index++) {

            if (first[index] == second[j]) {
                count++;
            } else if (first[index] != second[j] && count > 0) {
                break;
            }
        }
        if (count == second.length) {
            matchCount++;
        }
    }
    return matchCount;
}

Upvotes: 0

khelwood
khelwood

Reputation: 59146

Here's the way that is most readable for me:

public static int countOccurrences(String string, String sub) {
    int count = 0;
    int i = string.indexOf(sub);
    while (i >= 0) {
        ++count;
        i = string.indexOf(sub, i+1);
    }
    return count;
}

Upvotes: 1

Mojtaba Haddadi
Mojtaba Haddadi

Reputation: 1376

does this code help?

public static void main(String[] args) {
        String myString = "XLXXXLXX";
        int fromIndex = -1;
        int count = 0;
        while (true) {
            fromIndex = myString.indexOf("XX", fromIndex + 1);
            if (fromIndex != -1) {
                count++;
            } else {
                break;
            }
        }

        System.out.println(count);
    }

Upvotes: 0

user4910279
user4910279

Reputation:

Try this.

public static int count(String s, String f) {
    int count = 0;
    int end = s.length() - f.length();
    for (int i = 0; i <= end; ++i)
        if (s.startsWith(f, i))
            ++count;
    return count;
}

Upvotes: 0

azurefrog
azurefrog

Reputation: 10945

An easy way is to use indexOf(String, int) to find each occurrence of the pattern you're looking for in the source string. Just make sure to increment the index you find it at, so that you don't keep finding the same one.

Using this method

public static int count(String source, String lookFor) {
    int count = 0;
    int i = -1;

    while (i != 0) {
        i = source.indexOf(lookFor, i) + 1;
        if (i != 0) count++;
    }
    return count;
}

I get this output when testing

public static void main(String[] args) {
    System.out.println(count("XLXXXLXX", "XX"));    // 3
    System.out.println(count("XXX", "XX"));         // 2
    System.out.println(count("X", "XX"));           // 0
}

Upvotes: 2

Related Questions