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

.Examples:

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