String Matching: Naive Algorithm

Some programs that you use everyday need to find occurrences of a string in a text.
Think about your preferred IDE or simply any text-editing program.
When you misspelling a variable name and you want to fix this, you need to find all the part of the text where the name is present and substitute it.

When you type ctrl + F in vscode you are going to do a string matching
  • T[s+1 : s+m] = P[1 : m]

The Naive Algorithm

Let’s see now a very simple (and inefficient) algorithm for string matching, the so called naive string-matching algorithm.

Pseudocode

NaiveStringMatcher(T,P):
n = length(T)
m = length(P)
FOR s = 0 to n-m do:
IF P[1 : m] == T[s+1 : s+m]:
print "Pattern occurs with shift " s

Golang implementation

Now we see how this naive algorithm can be implemented in golang.

func NaiveStringMatching(text string, pattern string) {   n := len(text)
m := len(pattern)
for s := 0; s < (n-m)+1; s++ {
if pattern == text[s:s+m] {
fmt.Println("Pattern occurs with shift", s)
}
}
}
Pattern occurs with shift 56
Pattern occurs with shift 148
Pattern occurs with shift 154
  • From position 148 to 148+5, T[148 : 148 + 5]
  • From 154 to 154 + 5, T[154 : 154 + 5]
func main() {
text := "Nel mezzo del cammin di nostra vita mi ritrovai per una selva oscura, ché la diritta via era smarrita. Ahi quanto a dir qual era è cosa dura esta selva selvaggia e aspra e forte che nel pensier rinova la paura!"
pattern := "selva"
NaiveStringMatching(text, pattern) fmt.Println("T[56:56+5] -> ", text[56:56+5])
fmt.Println("T[146:148+5] -> ", text[148:148+5])
fmt.Println("T[154:154+5] -> ", text[154:154+5])
}
// OUTPUT: go run main.go

Pattern occurs with shift 56
Pattern occurs with shift 148
Pattern occurs with shift 154
T[56:56+5] -> selva
T[146:148+5] -> selva
T[154:154+5] -> selva

And now?

There are other types of string matching algorithm that works better.
The main defect of the Naive Algorithm is that it ignores the information gained on a value of s when it consider other values of s.
In the next posts, we will see other algorithms, like the Knuth-Morris-Pratt algorithm and another one that uses finite automata.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store