• 内存字符串暴力搜索定位代码
  • 1.1 Boyer-Moore实现
  • 1.2 简化版Tuned Boyer-Moore
  • 1.3 KMP

内存字符串暴力搜索定位代码

其它优秀的字符串搜索代码:点击

使用说明:

一般都是四个参数,

参数1: 你要搜索的缓冲区

参数2: 参数1缓冲区的大小

参数3: 要搜索的字符串

参数4: 参数3的缓冲大小

代码实现

search.h

#pragma once


/*
function:
		Boyer-Moore字符匹配算法
Param:
@text 要搜索的缓冲区开始
@n 要搜索的缓冲区大小
@pattern 需要匹配的字符串
@m 需要匹配的字符串长度
*/
int BinarySearch(unsigned char *text, int n, unsigned char *pattern, int m);

.cpp实现

使用BinarySearch即可.

#pragma once
#include "search.h"


#define maxNum 256

#ifndef MIN
# define MIN(A,B) ((A)<(B)?(A):(B))
#endif
#ifndef MAX
# define MAX(A,B) ((A)>(B)?(A):(B))
#endif

void PreBmBc(unsigned  char *pattern, int m, int bmBc[])
{
	int i;
	for (i = 0; i < 256; i++) {//一个字符占八位，共256个字符，把所有字符都覆盖到，这里的初始化是将所有字符失配时的移动距离都赋值为m
		bmBc[i] = m;
	}
	for (i = 0; i < m - 1; i++) {//针对模式串pattern中存在的每一个字符，计算出它们最靠右的（非最后一个字符）地方距离串末尾的距离，即它们失配时该移动的距离,这一操作更新了初始化中一些字符的移动距离
		bmBc[pattern[i]] = m - 1 - i;
	}
}
/*
function:
		旧版的好后缀辅助数组（好后缀长度）求解方法
Param:
@pattern 需要匹配的字符串
@suff 好后缀辅助数组
@m 需要匹配的字符串长度
*/
void suffix_old(char *pattern, int m, int suff[])
{
	int i, j;
	suff[m - 1] = m;
	for (i = m - 2; i >= 0; i--) {
		j = i;
		while (j >= 0 && pattern[j] == pattern[m - 1 - i + j]) j--;
		suff[i] = i - j;
	}
}
/*
function:
		新版的好后缀辅助数组（好后缀长度）求解方法
Param:
@pattern 需要匹配的字符串
@suff 好后缀辅助数组
@m 需要匹配的字符串长度
*/
void suffix(unsigned char *pattern, int m, int suff[]) {
	int f, g, i;
	suff[m - 1] = m;
	g = m - 1;
	for (i = m - 2; i >= 0; --i) {
		if (i > g&&suff[i + m - 1 - f] < i - g)
			suff[i] = suff[i + m - 1 - f];
		else {
			if (i < g)
				g = i;
			f = i;
			while (g >= 0 && pattern[g] == pattern[g + m - 1 - f])
				--g;
			suff[i] = f - g;
		}
	}
}
/*
function:
		好后缀数组求解方法
Param:
@pattern 需要匹配的字符串
@bmGs 好后缀数组
@m 需要匹配的字符串长度
*/
void PreBmGs(unsigned char *pattern, int m, int bmGs[])
{
	int i, j;
	int suff[maxNum];
	// 计算后缀数组
	suffix(pattern, m, suff);
	// 先全部赋值为m，包含Case3
	for (i = 0; i < m; i++) {
		bmGs[i] = m;
	}
	// Case2
	j = 0;
	for (i = m - 1; i >= 0; i--) {
		if (suff[i] == i + 1) {
			for (; j < m - 1 - i; j++) {
				if (bmGs[j] == m)
					bmGs[j] = m - 1 - i;
			}
		}
	}
	// Case1
	for (i = 0; i <= m - 2; i++) {
		bmGs[m - 1 - suff[i]] = m - 1 - i;
	}
}
/*
function:
		Boyer-Moore字符匹配算法
Param:
@text 文本内容
@n 文本内容长度
@pattern 需要匹配的字符串
@m 需要匹配的字符串长度
*/
int BinarySearch(unsigned char *text, int n, unsigned char *pattern, int m)
{
	int * bmBc = new int[maxNum];
	int * bmGs = new int[m];
	PreBmBc(pattern, m, bmBc);
	PreBmGs(pattern, m, bmGs);
	int i, pos;
	pos = 0;
	while (pos <= n - m) {
		for (i = m - 1; i >= 0 && pattern[i] == text[i + pos]; i--);
		if (i < 0) {
			delete bmGs;
			delete bmBc;
			return &text[pos] - text;
		}
		else {
			pos += MAX(bmBc[text[i + pos]] - m + 1 + i, bmGs[i]);
		}
	}
	return -1;
}

1.1 Boyer-Moore实现

上面的代码是有注释,也是这个相同实现

void preBmBc(char *x, int m, int bmBc[]) {
   int i;
 
   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}
 
 
void suffixes(char *x, int m, int *suff) {
   int f, g, i;
 
   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;
         while (g >= 0 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}
 
void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];
 
   suffixes(x, m, suff);
 
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}
 
 
void BM(char *x, int m, char *y, int n) {
   int i, j, bmGs[XSIZE], bmBc[ASIZE];
 
   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}

1.2 简化版Tuned Boyer-Moore

void TUNEDBM(char *x, int m, char *y, int n) {
   int j, k, shift, bmBc[ASIZE];
 
   /* Preprocessing */
   preBmBc(x, m, bmBc);
   shift = bmBc[x[m - 1]];
   bmBc[x[m - 1]] = 0;
   memset(y + n, x[m - 1], m);
 
   /* Searching */
   j = 0;
   while (j < n) {
      k = bmBc[y[j + m -1]];
      while (k !=  0) {
         j += k; k = bmBc[y[j + m -1]];
         j += k; k = bmBc[y[j + m -1]];
         j += k; k = bmBc[y[j + m -1]];
      }
      if (memcmp(x, y + j, m - 1) == 0 && j < n)
         OUTPUT(j);
      j += shift;                          /* shift */
   }
}

1.3 KMP

int attempt(char *y, char *x, int m, int start, int wall) {
   int k;

   k = wall - start;
   while (k < m && x[k] == y[k + start])
      ++k;
   return(k);
}


void KMPSKIP(char *x, int m, char *y, int n) {
   int i, j, k, kmpStart, per, start, wall;
   int kmpNext[XSIZE], list[XSIZE], mpNext[XSIZE],
       z[ASIZE];

   /* Preprocessing */
   preMp(x, m, mpNext);
   preKmp(x, m, kmpNext);
   memset(z, -1, ASIZE*sizeof(int));
   memset(list, -1, m*sizeof(int));
   z[x[0]] = 0;
   for (i = 1; i < m; ++i) {
      list[i] = z[x[i]];
      z[x[i]] = i;
   }

   /* Searching */
   wall = 0;
   per = m - kmpNext[m];
   i = j = -1;
   do {
      j += m;
   } while (j < n && z[y[j]] < 0);
   if (j >= n)
     return;
   i = z[y[j]];
   start = j - i;
   while (start <= n - m) {
      if (start > wall)
         wall = start;
      k = attempt(y, x, m, start, wall);
      wall = start + k;
      if (k == m) {
         OUTPUT(start);
         i -= per;
      }
      else
         i = list[i];
      if (i < 0) {
         do {
            j += m;
         } while (j < n && z[y[j]] < 0);
         if (j >= n)
            return;
         i = z[y[j]];
      }
      kmpStart = start + k - kmpNext[k];
      k = kmpNext[k];
      start = j - i;
      while (start < kmpStart ||
             (kmpStart < start && start < wall)) {
         if (start < kmpStart) {
            i = list[i];
            if (i < 0) {
               do {
                  j += m;
               } while (j < n && z[y[j]] < 0);
               if (j >= n)
                  return;
               i = z[y[j]];
            }
            start = j - i;
         }
         else {
            kmpStart += (k - mpNext[k]);
            k = mpNext[k];
         }
      }
   }
}