Scribd
Upload
4 views20 pages

String Matching 1

Module 06 covers various string matching algorithms including Naive String Matching, Finite Automata Matcher, Rabin Karp, Knuth Morris Pratt, Tries, Suffix Tree, and Suffix Array. It highlights real-world applications such as DNA pattern searching and internet search engines. The document also provides examples and algorithms for Naive String Matching and Finite Automata Matching, along with their time complexities.

Uploaded by

akshay.poswal.8791
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views20 pages

String Matching 1

Module 06 covers various string matching algorithms including Naive String Matching, Finite Automata Matcher, Rabin Karp, Knuth Morris Pratt, Tries, Suffix Tree, and Suffix Array. It highlights real-world applications such as DNA pattern searching and internet search engines. The document also provides examples and algorithms for Naive String Matching and Finite Automata Matching, along with their time complexities.

Uploaded by

akshay.poswal.8791
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Module 06: String Algorithms

Module Outline:
• Naive String Matching
• Finite Automata Matcher
• Rabin Karp matching algorithm
• Knuth Morris Pratt
• Tries
• Suffix Tree
• Suffix Array
Introduction

Some real world applications:


• Searching particular patterns in DNA sequences.
• In internet search engines to find Web pages relevant to input queries.
• Electronic surveillance
Example:
Terminology:
Naïve String Matching
Problem: Given a String Text[0..n-1] and a String Pattern[0..m-1], find
all occurrences of Pattern[] in Text[]. You may assume that n > m.
Examples:
Input1: Text[] = “TODAY IS A GOOD DAY”, Pattern[] = “GOOD”
Output1: Pattern found at index 11
Input2: Text[] = “A FRIEND IN NEED IS A FRIEND INDEED”, Pattern[] =
“FRIEND”
Output2: Pattern found at index 2, Pattern found at index
22
Naïve String Matching Algorithm:
Naïve_String_Matcher(pattern, text) {
int M = strlen(pattern); int N = strlen(text);
for (int s = 0; s <= N - M; s++) {
for (int j = 0; j < M; j++)
if (text [s + j] != pattern[j])
break;
if (j == M)
printf("Pattern found at index %d \n", s);
}
}
Time Complexity: O(N*M)
Example:
Finite Automata Matcher
Example:
Construction of string-matching automaton.
Basic Idea:
Example:
Algorithm for FA string matching:
Computation of transition function:
Running Time of
Compute-Transition-Function

Running Time: O(m3 |Σ|)


Outer loop: m |Σ|
Inner loop: runs at most m+1
Pk ⊃ Pqa: requires up to m comparisons
Improving Running Time
Much faster procedures for computing the transition function exist. The
time required to compute P can be improved to O(m|Σ|).
The time it takes to find the string is linear: O(n).

This brings the total runtime to:


O(n + m|Σ|)
Not bad if your string is fairly small relative to the text you are searching in.
Exercise:
Given pattern P=abba, Σ={a,b}, construct its automaton.
Show how the automaton works for text T[1..12]=baabbabbaaba.

You might also like