C Program to Repeatedly Search the Same Text

This is a C Program to search a string repeatitively. Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

Here is source code of the C Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure). The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define NO_OF_CHARS 256
  4.  
  5. int getNextState(char *pat, int M, int state, int x) {
  6.     // If the character c is same as next character in pattern,
  7.     // then simply increment state
  8.     if (state < M && x == pat[state])
  9.         return state + 1;
  10.  
  11.     int ns, i; // ns stores the result which is next state
  12.  
  13.     // ns finally contains the longest prefix which is also suffix
  14.     // in "pat[0..state-1]c"
  15.  
  16.     // Start from the largest possible value and stop when you find
  17.     // a prefix which is also suffix
  18.     for (ns = state; ns > 0; ns--) {
  19.         if (pat[ns - 1] == x) {
  20.             for (i = 0; i < ns - 1; i++) {
  21.                 if (pat[i] != pat[state - ns + 1 + i])
  22.                     break;
  23.             }
  24.             if (i == ns - 1)
  25.                 return ns;
  26.         }
  27.     }
  28.  
  29.     return 0;
  30. }
  31.  
  32. /* This function builds the TF table which represents Finite Automata for a
  33.  given pattern  */
  34. void computeTF(char *pat, int M, int TF[][NO_OF_CHARS]) {
  35.     int state, x;
  36.     for (state = 0; state <= M; ++state)
  37.         for (x = 0; x < NO_OF_CHARS; ++x)
  38.             TF[state][x] = getNextState(pat, M, state, x);
  39. }
  40.  
  41. /* Prints all occurrences of pat in txt */
  42. void search(char *pat, char *txt) {
  43.     int M = strlen(pat);
  44.     int N = strlen(txt);
  45.  
  46.     int TF[M + 1][NO_OF_CHARS];
  47.  
  48.     computeTF(pat, M, TF);
  49.  
  50.     // Process txt over FA.
  51.     int i, state = 0;
  52.     for (i = 0; i < N; i++) {
  53.         state = TF[state][txt[i]];
  54.         if (state == M) {
  55.             printf("Pattern found at index %d\n", i - M + 1);
  56.         }
  57.     }
  58. }
  59.  
  60. // Driver program to test above function
  61. int main() {
  62.     char *txt = "AABAACAADAABAAABAA";
  63.     char *pat = "AABA";
  64.     search(pat, txt);
  65.     return 0;
  66. }

Output:

$ gcc RepeatedStringSearch.c
$ ./a.out
 
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.