Skip to content

Instantly share code, notes, and snippets.

@phyous
Created October 5, 2012 16:11
Show Gist options
  • Save phyous/3840770 to your computer and use it in GitHub Desktop.
Save phyous/3840770 to your computer and use it in GitHub Desktop.
Algorithm to find # of occurrences of a substring in a given input string
/* Problem: Find # of occurrences of a substring in a given input string
Example Output:
Test string: abcdabceabcfabcabcd
Substring count for abc:5
Substring count for abcd:2
*/
public class CountSubs {
public static void main(String[] args) {
String testString = "abcdabceabcfabcabcd";
System.out.println("Test input string: " + testString);
String test1 = "abc";
String test2 = "abcd";
System.out.println("Substring count for " + test1 + ":" + findSubstringCount(testString, test1));
System.out.println("Substring count for " + test2 + ":" + findSubstringCount(testString, test2));
}
public static int findSubstringCount(String input, String substr) {
if (input.isEmpty() || input == null || substr.isEmpty() || substr == null) return 0;
int count = 0, subPrt = 0, subLength = substr.length();
for (char c : input.toCharArray()) {
if (substr.charAt(subPrt) == c) {
subPrt++;
if (subPrt == subLength) {
count++;
subPrt = 0;
}
} else {
if (c == substr.charAt(0))
subPrt = 1;
else
subPrt = 0;
}
}
return count;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment