\n This is a problem to find how many times a specific pattern appears in a given string. \n Returns the total count of how many times \n To solve this problem, a string search algorithm must be used. \n One of the ways to efficiently solve the string search problem is by using the KMP (Knuth-Morris-Pratt) algorithm. \n The LPS array indicates how much the prefix and suffix match within the pattern. This allows for the pattern to be reused during the search. Now, based on the above process, we will implement the string search algorithm in Java.<\/p>\n
\n For example, determining how many times the pattern \"ana\"<\/code> appears in the string \"banana\"<\/code>.\n <\/p>\nInput<\/h3>\n
\n
text<\/code>: The entire string to search (1 \u2264 |text| \u2264 100,000)<\/li>\npattern<\/code>: The string to find (1 \u2264 |pattern| \u2264 50)<\/li>\n<\/ul>\nOutput<\/h3>\n
pattern<\/code> appears in the string text<\/code>.\n <\/p>\nExample<\/h2>\n
Input<\/h3>\n
text = \"banana\"\npattern = \"ana\"<\/code><\/pre>\nOutput<\/h3>\n
2<\/code><\/pre>\nSolution Process<\/h2>\n
\n The simplest way is to traverse the string one character at a time and compare the pattern, but this is inefficient and has a time complexity of O(n*m) for large data.\n <\/p>\nEfficient Solution: KMP Algorithm<\/h3>\n
\n This algorithm consists of the following two parts:\n <\/p>\n\n
Generating the LPS Array<\/h4>\n
\n For example, if the pattern is \"ABAB\"<\/code>, the LPS array will be [0, 0, 1, 2]<\/code>.\n <\/p>\nAlgorithm Implementation<\/h4>\n
public class KMP {\n public static int[] computeLPS(String pattern) {\n int[] lps = new int[pattern.length()];\n int length = 0; \n int i = 1;\n \n while (i < pattern.length()) {\n if (pattern.charAt(i) == pattern.charAt(length)) {\n length++;\n lps[i] = length;\n i++;\n } else {\n if (length != 0) {\n length = lps[length - 1];\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n return lps;\n }\n\n public static int KMPsearch(String text, String pattern) {\n int[] lps = computeLPS(pattern);\n int i = 0; \n int j = 0; \n int count = 0;\n\n while (i < text.length()) {\n if (pattern.charAt(j) == text.charAt(i)) {\n i++;\n j++;\n\n if (j == pattern.length()) {\n count++;\n j = lps[j - 1];\n }\n } else {\n if (j != 0) {\n j = lps[j - 1];\n } else {\n i++;\n }\n }\n }\n return count;\n }\n\n public static void main(String[] args) {\n String text = \"banana\";\n String pattern = \"ana\";\n int result = KMPsearch(text, pattern);\n System.out.println(\"Substring Count: \" + result);\n }\n}<\/code><\/pre>\nCode Explanation<\/h2>\n