Scribd
Upload
36 views9 pages

At Aba 1

The document discusses a finite automata algorithm for pattern searching in text. It describes building a transition function table representing a finite automaton from the pattern and using it to search for the pattern in text in linear time.

Uploaded by

Chinmayi HS
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
36 views9 pages

At Aba 1

The document discusses a finite automata algorithm for pattern searching in text. It describes building a transition function table representing a finite automaton from the pattern and using it to search for the pattern in text in linear time.

Uploaded by

Chinmayi HS
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
You are on page 1/ 9

AUTOMATA THEORY (20CS53)

ACTIVITY BASED ASSESSMENT

TOPIC : FINITE AUTOMATA ALGORITHM


FOR PATTERN SEARCHING

BY :

CHAITHANYA S 4VV20CS021
CHINMAYI H 4VV20CS024
HAMSINI D 4VV20CS046
Pattern searching

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
In FA based algorithm, we preprocess the pattern and
build a 2D array that represents a Finite Automata.

1. In search, we simply need to start from the first state of


the automata and the first character of the text.

2. At every step, we consider next character of text,


look for the next state in the built FA and move to a
new
3. state.

4. If we reach the final state, then the pattern is found


in the text.

The time complexity of the search process is O(n).

Before we discuss FA construction, let us take a look at


the following FA for pattern ACACAGA.
The above diagrams represent graphical and tabular
representations of pattern ACACAGA.

Number of states in FA will be M+1 where M is length of


the pattern. The main thing to construct FA is to get the
next state from the current state for every possible
character.

Given a character x and a state k :

• we can get the next state by considering the string


“pat [0..k-1]x” which is basically concatenation of
pattern characters pat[0], pat[1] … pat[k-1] and the
character x.
• The idea is to get length of the longest prefix of the
given pattern such that the prefix is also suffix of
“pat[0.. k-1]x”.

• The value of length gives us the next state.

• For example :
Let us see how to get the next state from current state 5
and character ‘C’ in the above diagram.
1. We need to consider the string, “pat[0..4]C” which is
“ACACAC”.

2. The length of the longest prefix of the pattern such


that the prefix is suffix of “ACACAC”is 4 (“ACAC”).

3. So the next state (from state 5) is 4 for character ‘C’.


// C program for Finite Automata Pattern searching
// Algorithm
#include<stdio.h>
#include<string.h>
#define NO_OF_CHARS 256

int getNextState(char *pat, int M, int state, int x)


{
// If the character c is same as next character
// in pattern,then simply increment state
if (state < M && x == pat[state])
return state+1;

// ns stores the result which is next state


int ns, i;

// ns finally contains the longest prefix


// which is also suffix in "pat[0..state-1]c"
// Start from the largest possible value
// and stop when you find a prefix which
// is also suffix
for (ns = state; ns > 0; ns--)
{
if (pat[ns-1] == x)
{
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}

return 0;
}
/* This function builds the TF table which represents4
Finite Automata for a given pattern */
void computeTF(char *pat, int M, int TF[][NO_OF_CHARS])
{
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}

/* Prints all occurrences of pat in txt */


void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);

int TF[M+1][NO_OF_CHARS];

computeTF(pat, M, TF);

// Process txt over FA.


int i, state=0;
for (i = 0; i < N; i++)
{
state = TF[state][txt[i]];
if (state == M)
printf ("\n Pattern found at index %d “,i-M+1);
}
}
// Driver program to test above function
int main()
{
char *txt = "AABAACAADAABAAABAA";
char *pat = "AABA";
search(pat, txt);
return 0;
}

Output:

Pattern found at index 0


Pattern found at index 9
Pattern found at index 13

Time Complexity: O(m2)


Auxiliary Space: O(m)

You might also like