count directly repeated substring occurence

Question

I am trying to count the number of directly repeatings of a substring in a string.

String s = "abcabcdabc";
String t = "abc";
int count = 2;

EDIT: because some people are asking, i try to clarify this: there are 3 times t in s but i need the number of times t is repeated without any other character. that would result in 2, because the d in my example is not the starting character of t. ('d' != 'a').

Another example to clarify this:

String s = "fooabcabcdabc";
String t = "abc";
int count = 0;

I know how to count the number of occurrences in the string, i need it to be repeating from left to right without interruption!

Here is what i have so far, but i think i made a simple mistake in it...

public static int countRepeat(String s, String t){
    if(s.length() == 0 || t.length() == 0){
        return 0;
    }
    int count = 0;
    if(t.length() == 1){
        System.out.println(s+" | " + t);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(0)){
                return count;
            }
            count++;
        }
    }else{
        System.out.println(s+" | " + t);
        for (int i = 0; i < s.length(); i++) {
            int tchar = (i- (count*(t.length()-1)));
            System.out.println(i+ " | " + tchar);
            if (s.charAt(i) != t.charAt(tchar)){
                return count;
            }
            if(tchar >= t.length()-1){
                count++;
            }
        }
    }
    return count;
}

what am i doing wrong? And is there a better/faster way to do this?

I know, but indexOf() is returning the first occurance which is at 0. Can you post a code example using indexOf() that is actually answering my question? — reggaemuffin, Feb 14 '14 at 12:02
Well, `String` also has `.subString()` ;) I still don't understand, though, what you mean by " count the number of directly repeatings"? — fge, Feb 14 '14 at 12:03
in my example, if you count the number of occurences, it would result 3 but it should result 2 because the d is not part of the substring. — reggaemuffin, Feb 14 '14 at 12:07
It shows 3 because the last `abc` is also a substring, even when it already passed `dabc`. It just continues from that and sees another `abc`. — Jeroen Vannevel, Feb 14 '14 at 12:11
You should use Regular Expressions. Check this post: http://stackoverflow.com/questions/7378451/java-regex-match-count — EternalTinkerer, Feb 14 '14 at 12:11

score 2 · Answer 1 · answered Feb 14 '14 at 12:04

2

There exists a str.indexOf(substring,index) method in the String API.

In pseudocode this would mean something like this:

declare integer variable as index 
declare integer variable as count
while index <= (length of string - length of substring)
  index = indexOf substring from index
  if index >= 0
    increment count
  end if
end while

answered Feb 14 '14 at 12:04

Jeroen Vannevel

43,651
22
107
170

this will simply count the number of times substring is represented in str and is not checking for interruption. – reggaemuffin Feb 14 '14 at 12:16
1

Yes, it wasn't clear from your question what the actual problem was. I have to leave for class now but I will check back on this question later tonight and see whether help is still needed. – Jeroen Vannevel Feb 14 '14 at 12:17

fge · Accepted Answer · 2014-02-15T00:04:05.080

1

Using indexOf() makes the code much easier:

public static int startingRepeats(final String haystack, final String needle)
{
    String s = haystack;
    final int len = needle.length();

    // Special case...
    if (len == 0)
        return 0;

    int count = 0;

    while (s.startsWith(needle)) {
        count++;
        s = s.subString(len);
    }

    return count;
}

edited Feb 15 '14 at 00:04

answered Feb 14 '14 at 12:07

fge

119,121
33
254
329

1

Note, you could also use `.startsWith()` instead of `.indexOf()` – fge Feb 14 '14 at 12:18
your code needs a check for len==0 because then you have an endless loop! – reggaemuffin Feb 14 '14 at 12:53

score 1 · Answer 3 · answered Feb 14 '14 at 12:23

This version does not allocate new objects (substrings, etc) and just look for the characters where they are supposed to be.

public static void main(String[] args) {
    System.out.println(countRepeat("abcabcabc", "abc")); //  3
    System.out.println(countRepeat("abcabcdabc", "abc")); // 2
    System.out.println(countRepeat("abcabcabcx", "abc")); // 3
    System.out.println(countRepeat("xabcabcabc", "abc")); // 0
}
public static int countRepeat(String s, String t){
    int n = 0; // Ocurrences
    for (int i = 0; i < s.length(); i ++) { // i is index in s
        int j = i % t.length(); // corresponding index in t
        boolean last = j == t.length() - 1; // this should be the last char in t
        if (s.charAt(i) == t.charAt(j)) { // Matches?
            if (last) { // Matches and it is the last
                n++;
            }
        } else { // Do not match. finished!
            break;
        }
    }
    return n;
}

I have compared your solution to fges solution and his is around 7 times faster than yours! Seems that using native functions has some benefits... — reggaemuffin, Feb 14 '14 at 12:45
I tried to write clean code and not fastest code but I expected this to be faster at least with this short strings and most of them being positive matches. — aalku, Feb 14 '14 at 12:48

score 0 · Answer 4 · answered Feb 14 '14 at 12:20

0

Here is the another calculator:

String s = "abcabcdabc";
String t = "abc";

int index = 0;
int count = 0;

while ((index = s.indexOf(t, index)) != -1) {
    index += t.length();
    count++;
}

System.out.println("count = " + count);

answered Feb 14 '14 at 12:20

Ashot Karakhanyan

2,804
3
23
28

count directly repeated substring occurence

4 Answers4