Created
October 5, 2012 16:11
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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