Java Program for Naive Pattern Searching Algorithm
Slide the pattern over text one by one and check for a match. If a match is found, then slide by 1 again to check for subsequent matches.
Java
// Java program for Naive Pattern Searching public class NaiveSearch { static void search(String pat, String txt) { int l1 = pat.length(); int l2 = txt.length(); int i = 0 , j = l2 - 1 ; for (i = 0 , j = l2 - 1 ; j < l1;) { if (txt.equals(pat.substring(i, j + 1 ))) { System.out.println( "Pattern found at index " + i); } i++; j++; } } // Driver's code public static void main(String args[]) { String pat = "AABAACAADAABAAABAA" ; String txt = "AABA" ; // Function call search(pat, txt); } } // This code is contributed by D. Vishnu Rahul Varma |
Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
Time Complexity: O(N2)
Auxiliary Space: O(1)
Java Program for Naive algorithm for Pattern Searching
Write a Java program for a given text string with length n and a pattern with length m, the task is to print all occurrences of the pattern in text.
Note: You may assume that n > m.
Examples:
Input: text = “THIS IS A TEST TEXT”, pattern = “TEST”
Output: Pattern found at index 10Input: text = “AABAACAADAABAABA”, pattern = “AABA”
Output: Pattern found at index 0, Pattern found at index 9, Pattern found at index 12