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

#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("%dn"),?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(",?%dn"),?next[i]); } else { j?=?next[j]; } } printf("n"); } int?kmp_bin(byte?main[],?int?mainSize,?byte?sub[],?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,?SEEK_SET);

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

	byte?t[]?=?{?";[email?protected]@!UTF-8!;[email?protected]@!"?};

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

	fclose(fp);
	delete?[]pBuff;
}