Boyer Moore String Searching Algorithm in C++

leothenerd 11:51 am on December 7, 2009 | Answers: 1    
Tags: algorithm (6), boyer, moore string, searching (2)

Rate Knowledge:

 Loading ...

• leothenerd 11:51 am on December 7, 2009
  

  
  int max(int x1, int x2)
  {  
    return (x1 > x2) ? x1 : x2;
  }
  
  void BadCharTable(string x, int m, int *tableBC) 
  {  
    for (int i = 0; i < 256; i++)
      tableBC[i] = m;
    for (int i = 0; i = 0; i--) 
    {
      if (i > g && (suff[i + m - 1 - f] < i - g))
        suff[i] = suff[i + m - 1 - f];
      else 
      {
        if (i = 0 && x[g] == x[g + m - 1 - f])
          g--;
        suff[i] = f - g;
      }
    }
  
    for (i = 0; i = 0; i--)
      if (suff[i] == i + 1)
        while (j < m - 1 - i)
        {
          if (tableGS[j] == m)
              tableGS[j] = m - 1 - i;
          j++;
        }
    for (i = 0; i <= m - 2; i++)
      tableGS[m - 1 - suff[i]] = m - 1 - i;
  }
   
  void BoyerMoore(string x, int m, string y, int n) 
  {  
    int i, j = 0, tableBC[256], tableGS[256];
     
    GoodSuffixTable(x, m, tableGS);
    BadCharTable(x, m, tableBC);
    
    while (j = 0 && x[i] == y[i + j]; i--);
      if (i < 0)
      {  // Match
        printf("Matches on %d position.\n", j);
        j += tableGS[0];
      }
      else
        j += max(tableGS[i], tableBC[y[i + j]] - m + 1 + i);
    }
  }