In computer science, string searching algorithms, sometimes called string matching algorithms, that try to find a place where one or several string (also called pattern) are found within a larger string or text.
STRING MATCHING PROBLEM
Naïve pattern searching is the simplest method among other pattern searching algorithms. It checks for all character of the main string to the pattern.
This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find substring by checking once for the string. It also does not occupy extra space to perform the operation.
The time complexity of Naïve Pattern Search method is O(m*n). The m is the size of pattern and n is the size of the main string
When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat, char txt) that prints all occurrences of pat in txt. You may assume that n > m
Input: txt = "THIS IS A TEST TEXT"
pat = "TEST"
Output: Pattern found at index 10
Input: txt = "AABAACAADAABAABA"
pat = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
THE NAIVE ALGORITHM The naive algorithm finds all valid shifts using a loop that checks the condition P[1….m]=T[s+1…. s+m] for each of the nm+1 possible values of s.(P=pattern ,
T=text/string , s=shift) NAIVE-STRING-MATCHER(T,P)
1) n = T.length
2) m = P.length
3) for s=0 to n-m
4) if P[1…m]==T[s+1….s+m]
5) printf” Pattern occurs with shift ” s
EXAMPLE : SUPPOSE, T=1011101110 , P=111 FIND ALL VALID SHIFT