C Program Finds Sub-String Search in String

C Program Finds Sub-String Search in String

How to write a C Program to Finds Sub-String Search in String in C Programming Language ?

This C Program to Finds sub-string search in string s.
Returns -1 if sub-string was not found
Returns 0 if search was empty
Returns starting index of sub-string if successful

Solution:

  1. int find(string s, string search)
  2. {
  3.         if(length(search) == 0)
  4.         {
  5.                 return 0;
  6.         }
  7.  
  8.         int s_index = 0; //Starting index
  9.         int c_index = 0; //Checking index
  10.         int b_table[length(search)]; //Backtracking table
  11.         fill_backtrack_table(*b_table, search);
  12.  
  13.         while(length(s) >= (s_index + c_index))
  14.         {
  15.                 if(s.src[s_index + c_index] == search.src[c_index])
  16.                 {
  17.                         if(c_index == length(search) - 1)
  18.                         {
  19.                                 return s_index;
  20.                         }
  21.                         else
  22.                         {
  23.                                 c_index++;
  24.                         }
  25.                 }
  26.                 else
  27.                 {
  28.                         if(b_table[c_index] == -1)
  29.                         {
  30.                                 s_index++;
  31.                                 c_index = 0;
  32.                         }
  33.                         else
  34.                         {
  35.                                 s_index += c_index - b_table[c_index];
  36.                                 c_index = b_table[c_index];
  37.                         }
  38.                 }
  39.         }*/
  40.         return -1;
  41. }
  42.  
  43. // Fills the backtrack table for function find
  44. void fill_backtrack_table(int* b_table, string search)
  45. {
  46.         b_table[0] = -1;
  47.         if(length(search) == 1)
  48.         {
  49.                 return;
  50.         }
  51.         b_table[1] = 0;
  52.  
  53.         int t_index = 2; //Table index
  54.         int s_index = 0; //Search index
  55.  
  56.         while (t_index < length(search))
  57.         {
  58.                 if(search.src[t_index - 1] == search.src[s_index])
  59.                 {
  60.                         b_table[t_index] = s_index + 1;
  61.                         s_index++;
  62.                         t_index++;
  63.                 }
  64.                 else if(s_index > 0)
  65.                 {
  66.                         s_index = b_table[s_index];
  67.                 }
  68.                 else
  69.                 {
  70.                         b_table[t_index] = 0;
  71.                         t_index++;
  72.                 }
  73.         }
  74.         return;
  75. }


Learn More :