Problem Statement
What is the time complexity of the naive substring search algorithm for text of length n and pattern of length m?
Explanation
The naive substring search checks for pattern match starting at each position in the text, leading to O(n*m) time in the worst case. More efficient algorithms like KMP reduce this to O(n+m).
Code Solution
SolutionRead Only
int search(String text,String pat){
int n=text.length(),m=pat.length();
for(int i=0;i<=n-m;i++){
int j=0; while(j<m && text.charAt(i+j)==pat.charAt(j)) j++;
if(j==m) return i; }
return -1; }Practice Sets
This question appears in the following practice sets:
