What is the algorithm that the "Find" feature in Notepad or any other simple text editor uses?

Question

To quickly find words in large volumes of text, we just enter the keyword in the "Find" feature of Notepad or a similar text editor. The function finds in the desired word, if its in text, in a fraction of a second.

It cant be a sequential word by word search..it would have takem too long. It cant be binary search. Then what is it?

Can anybody out there please tell me what is the algorithm that the function this "Find" feature uses?

Answer 1

Notepad, MS Word, etc use what is called a Regular expression engine. There could be a book made about the algorithm used. Notepad uses a dumbed dowm version of the Regex engine but it allows you to search for simple word patterns: i.e. "Hello"

Try using MS word and open the find dialog box. You will see a checkbox for wildcards: check it.

type this into find:
[Hello] Notice the brackets.

This will find any instance of h, any instance of e, any instance of L, Etc....

Using regular expressions in MS word is a little limited but still it is there. Do a search in MS word for help on the find dialog box. You will be amazed at some of the simple things that you can do.

Remember the engine is actually looking for a pattern, not a word or character even though it seems like it is only trying to find simple words.

A little background:

Stephen Kleene invented Regular expressions in the 1950s.

Google regular expressions also to get a little background.
Dont dive too deep into how the patterns are used unless you are a programmer.

Hope this helps you

Answer 2

It isn't character by character...the algorithms are smarter then that by now.

Look up the Knutt-Morris-Pratt algorithm for more details.

Answer 3

It's a plain old character-by-character scan of the text. It doesn't take long -- computers are pretty fast these days.

Answer 4

I'm sure it is a Boyer-Moore algorithm or something derived from it.

Answer 5

Take a look at this link.