NAME: MANIPRIYAA R

REG NO: 23BAI0214

1.Rabin-Karp Algorithm (C Implementation)

#include <string.h>

#define d 256

void rabinKarp(char pattern[], char text[], int q) {

int M = strlen(pattern);

int N = strlen(text);

int p = 0, t = 0, h = 1;

int i, j;

for (i = 0; i < M - 1; i++)

h = (h * d) % q;

for (i = 0; i < M; i++) {

p = (d * p + pattern[i]) % q;

t = (d * t + text[i]) % q;

}// Slide the pattern over the text

for (i = 0; i <= N - M; i++) {

if (p == t) {

for (j = 0; j < M; j++)

if (text[i + j] != pattern[j])

break;

if (j == M)

printf("Pattern found at index %d\n", i);

if (i < N - M) {

t = (d * (t - text[i] * h) + text[i + M]) % q;

if (t < 0) t += q; }}}
int main() {

char text[] = "ABCCDEABCDABCD";

char pattern[] = "ABCD";

int q = 101; // Prime number

rabinKarp(pattern, text, q);

return 0;

1. Understanding the Algorithm

 The Rabin-Karp algorithm is a pattern-searching algorithm that uses hashing to find

 It calculates the hash value of the pattern and compares it with the hash values of substrings of
the text.

2. Defining Key Parameters

 The text and pattern lengths are calculated.

 Variables are initialized to store the hash values of the pattern and the current substring of the
text.

 h is a factor used in hash value calculations.

3. Precomputing the Hash Factor (h)

 A helper value h = (d^(M-1)) % q is computed.

 This helps in efficiently removing the first character and adding a new character while
updating the rolling hash

4. Calculating Initial Hash Values

 The hash values of the pattern and the first window of text (of the same length as the pattern)
are computed.

 This avoids comparing the pattern character-by-character initially.

5. Sliding the Pattern Over the Text

 The algorithm moves the pattern one character at a time over the text.
  If the hash values match, a character-by-character comparison is performed to confirm the
match.

6. Rolling Hash Technique

 Instead of recalculating the hash from scratch for each new substring, the hash is updated using
the rolling hash formula:

o Remove the first character's contribution.

o Add the new character at the end.

 This reduces redundant computations and makes the algorithm efficient.

7. Handling Negative Hash Values

 If the updated hash value becomes negative, a small adjustment is made to convert it into a
positive value.

8. Output the Match Index

 If a pattern match is found, the index of occurrence is printed.

9. Main Function Execution

 A sample text ("ABCCDEABCDABCD") and pattern ("ABCD") are given.

 The Rabin-Karp function is called, and it finds all occurrences of "ABCD" in the text.

10. Time Complexity

 Best case: O(N)O(N)O(N) (when there are few hash collisions).

 Worst case: O(NM)O(NM)O(NM) (when many hash collisions occur, leading to character-by-
character comparisons).

 Average case: O(N)O(N)O(N) (efficient due to hashing).

2. Knuth-Morris-Pratt (KMP) Algorithm

#include <string.h>
void computeLPSArray(char* pattern, int M, int* lps) {

int len = 0, i = 1;

lps[0] = 0;

while (i < M) {

if (pattern[i] == pattern[len]) {

len++;

lps[i] = len;

i++;

} else {

if (len != 0)

len = lps[len - 1];

else {

lps[i] = 0;

i++}}}}

void KMPSearch(char* pattern, char* text) {

int M = strlen(pattern);

int N = strlen(text);

int lps[M];

computeLPSArray(pattern, M, lps);

int i = 0, j = 0;

while (i < N) {

if (pattern[j] == text[i]) {

i++;

j++;

}
 if (j == M) {

printf("Pattern found at index %d\n", i - j);

j = lps[j - 1];

} else if (i < N && pattern[j] != text[i]) {

if (j != 0)

j = lps[j - 1];

else

i++;}}}

int main() {

char text[] = "ABABDABACDABABCABAB";

char pattern[] = "ABABCABAB";

KMPSearch(pattern, text);

return 0;}

1. Compute the LPS (Longest Prefix Suffix) Array

 The LPS array helps determine how much the pattern should be shifted when a mismatch occurs.

 It stores the length of the longest proper prefix which is also a suffix for each prefix of the
pattern.

 If a mismatch happens, the LPS array tells where to resume the comparison instead of restarting
from the beginning.

2. Constructing the LPS Array

 Start with the first character (lps[0] = 0).

 Compare the current character with the last matched prefix character:

o If they match, extend the LPS length and update lps[i].

o If they don’t match, reduce the prefix length using previous LPS values until a match is
found or reset to zero.
  Continue until the entire pattern is processed.

3. Searching the Pattern in the Text

 Traverse the text and compare it with the pattern.

 If characters match, move both pointers forward.

 If a complete match occurs, print the index and use lps[j-1] to determine how much to shift.

 If a mismatch occurs:

o Use the LPS array to avoid unnecessary rechecking.

o Move the pattern according to lps[j-1], instead of shifting it back completely.

4. Time Complexity

 Preprocessing (LPS Calculation): O(M)O(M)O(M)

 Pattern Matching: O(N)O(N)O(N)

 Overall Complexity: O(N+M)O(N + M)O(N+M), making KMP much faster than naive string-
matching algorithms.

5. Key Advantage

 Unlike brute force methods, KMP doesn’t backtrack in the text, making it highly efficient for
searching in large strings.

3. Automata-Based String Matching Algorithm

#include <string.h>

#define NO_OF_CHARS 256

void computeTF(char* pattern, int M, int TF[][NO_OF_CHARS]) {

int i, lps = 0, x;
 for (x = 0; x < NO_OF_CHARS; x++)

TF[0][x] = 0;

TF[0][pattern[0]] = 1;

for (i = 1; i < M; i++) {

for (x = 0; x < NO_OF_CHARS; x++)

TF[i][x] = TF[lps][x];

TF[i][pattern[i]] = i + 1;

if (i > 0)

lps = TF[lps][pattern[i]]; }

for (x = 0; x < NO_OF_CHARS; x++)

TF[M][x] = TF[lps][x];}

void search(char* text, char* pattern) {

int M = strlen(pattern);

int N = strlen(text);

int TF[M + 1][NO_OF_CHARS];

computeTF(pattern, M, TF);

int state = 0, i;

for (i = 0; i < N; i++) {

state = TF[state][text[i]];

if (state == M)

printf("Pattern found at index %d\n", i - M + 1);}}

int main() {

char text[] = "AABAACAADAABAABA";

char pattern[] = "AABA";

search(text, pattern);

return 0;
}

1. Transition Function (TF) Table Construction

 The Transition Function (TF) table determines the next state based on the current state and the
incoming character.

 It ensures that when a mismatch occurs, the algorithm jumps to the longest prefix which is also a
suffix of the matched portion.

Steps for Building the TF Table:

1. Initialize the table: Set all transitions for state 0 to 0, except for the first character.

2. Iterate through the pattern:

o Copy transitions from the longest prefix suffix (LPS) state.

o Update the transition for the current character.

o Update the LPS state using previous transitions.

3. Final state transitions: Ensure that the last row contains proper shift values to continue pattern
matching efficiently.

2. Pattern Matching Process

 Start from state 0.

 For each character in the text:

o Move to the next state using the TF table.

o If the final state (equal to pattern length) is reached, a match is found.

3. Time Complexity

 Preprocessing (TF Table Construction): O(M×NO_OF_CHARS)O(M \times

 Pattern Matching: O(N)O(N)O(N) where NNN is the text length.

 Overall Complexity: O(M×NO_OF_CHARS+N)O(M \times \text{NO\_OF\_CHARS} +

4. Key Advantages
  Efficient searching: Uses precomputed shifts, avoiding unnecessary comparisons.

 No backtracking: Unlike brute force methods, FA ensures smooth state transitions.

5. Example Execution

 Text: "AABAACAADAABAABA"

 Pattern: "AABA"

 The algorithm quickly identifies matches at indices 0, 9, and 12 by efficiently shifting the pattern