KMP二进制算法在文件搜索中的应用

发布时间:2020-08-03 18:13:34 作者:Chinayu2014
来源:网络 阅读:1250
#define ARRAY_NUM(a)	((sizeof(a))/(sizeof(a[0])))
typedef unsigned char	byte;

void getnext_bin(byte sub[], int subSize, int next[])
{
	// 得到next数据,其实本质是自身KMP匹配
	printf("sub bin array : ");
	int i, j;
	i = 0;
	j = -1;
	next[0] = -1;
	TRACE(_T("%d\n"), next[i]);
	while (i + 1 < subSize)
	{
		if (j == -1 || sub[i] == sub[j])
		{
			++i;
			++j;
#if 1
			if (sub[i] != sub[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}

#else
			next[i] = j;
#endif
			TRACE(_T(", %d\n"), next[i]);
		}
		else
		{
			j = next[j];
		}

	}
	printf("\n");
}


int kmp_bin(byte main[], int mainSize, byte sub[], int subSize, int next[])
{
	// 返回s在m中的第一个数据的下标
	int i, j;
	i = 0;
	j = 0;
	int nIndex = -1;
	while (i < mainSize)
	{
		if (j == -1 || main[i] == sub[j])
		{
			++i;
			++j;
			if (j == subSize)
			{
				nIndex = (i - j);
				break;
			}
		}
		else
		{
			j = next[j];
		}
	}
	return nIndex;
}

调用方法:

void CtestDlg::OnBnClickedButton2()
{
	FILE  * fp;
	_wfopen_s(&fp, _T("c:\\Install.exe"), _T("rb"));

	fseek(fp, 0, SEEK_END);
	INT  length = ftell(fp);

	fseek(fp, 0, SEEK_SET);

	byte *pBuff = new byte[length];
	memset(pBuff, 0, length);
	fread(pBuff, length, 1, fp);

	byte t[] = { ";!@Install@!UTF-8!;!@InstallEnd@!" };

	// 二进制序列的KMP
	int next[ARRAY_NUM(t)] = { 0 };
	getnext_bin(t, sizeof(t), next);
	TRACE("kmp_bin  = %d\n", kmp_bin(pBuff, length, t, 33, next));

	fclose(fp);
	delete []pBuff;
}


推荐阅读:
  1. 泛型KMP算法
  2. KMP算法的详细解释及实现

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

kmp 应用 搜索

上一篇:django优秀资源推荐

下一篇:msyql数据表的操作

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》