一个基于KMP优化算法的数据块匹配算法类
本帖最后由 lucky_789 于 2015-6-2 23:13 编辑KMP算法大家都知道是一种改进的字符串匹配算法，我这里将其略作修改，使其能作数据块匹配，即不限于字符串匹配，并封装成类。
本算法类主要参考并基于July的博文《从头到尾彻底理解KMP》(http://blog.csdn.net/v_july_v/article/details/7041827)// KmpDataSearch.h: Search data block from another and return the FIRST matched location.
//
//////////////////////////////////////////////////////////////////////
/********************************************************************/
/* 单元名称: KmpSearchData类 */
/* 单元作者: lucky_789 */
/* 说 明: 修改自July的KMP优化算法 */
/********************************************************************/
#if !defined(AFX_KmpSearchData_H__INCLUDED_)
#define AFX_KmpSearchData_H__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif
#include <windows.h>
class KmpSearchData
{
public:
int WINAPI KmpSearch(char* s, int sSize, char* p, int pSize);
void GetNext(char* p, int sSize, int next[]) ;
KmpSearchData();
virtual ~KmpSearchData();
};
#endif // !defined(AFX_KmpSearchData_H__INCLUDED_)
// KmpDataSearch.cpp: Search data block from another and return the FIRST matched location.
//
//////////////////////////////////////////////////////////////////////
/********************************************************************/
/* 单元名称: KmpSearchData类 */
/* 单元作者: lucky_789 */
/* 说 明: 修改自July的KMP优化算法 */
/********************************************************************/
#include "KmpSearchData.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
KmpSearchData::KmpSearchData()
{
}
KmpSearchData::~KmpSearchData()
{
}
/**************************************************************************/
/* 函数名称: KmpSearch */
/* 函数作者: lucky_789 */
/* 函数参数: s: 要在其中查找目标数据的源数据块 */
/* sSize:源数据块的字节数。中间可能存在'\0',故不能用strlen(s) */
/* p: 查找的模式数据块(在s中查找p的位置) */
/* pSize:查找的模式数据块大小(字节数) */
/**************************************************************************/
int WINAPI KmpSearchData::KmpSearch(char *s, int sSize, char *p, int pSize)
{
int i = 0;
int j = 0;
int sLen = sSize;
int pLen = pSize;
int *next = new int;
memset(next, 0, pSize * sizeof(int));
GetNext(p, pSize, next);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S == P），都令i++，j++
if (j == -1 || s == p)
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S != P），则令 i 不变，j = next
//next即为j所对应的next值
j = next;
}
}
delete next;
if (j == pLen)
return i - j;
else
return -1;
}
/**************************************************************************/
/* 函数名称: GetNext */
/* 函数作者: lucky_789 */
/* 函数参数: p: 查找的模式数据块(在s中查找p的位置) */
/* pSize:查找的模式数据块大小(字节数) */
/* next: 优化过后的next数组 */
/**************************************************************************/
void KmpSearchData::GetNext(char *p, int pSize, int next[])
{
int pLen = pSize;
next = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p表示前缀，p表示后缀
if (k == -1 || p == p)
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p != p)
next = k; //之前只有这一行
else
//因为不能出现p = p[ next]，所以当出现时需要继续递归，k = next = next]
next = next;
}
else
{
k = next;
}
}
}
#include <iostream>
#include "KmpSearchData.h"
using namespace std;
KmpSearchData KmpSearch;
int main()
{
char szbuf = {0};
char s =
{
0x00, 0x00, 0xbd, 0x10, 0x00, 0x00, 0x00, 0xc7, 0x44, 0x24, 0x44, 0x08, 0x00, 0x00, 0x00, 0x8b,\
0x54, 0x24, 0x44, 0x89, 0x54, 0x24, 0x30, 0xbb, 0x01, 0x00, 0x00, 0x00, 0x90, 0x3d, 0x00, 0x00,\
0x00, 0x01, 0x73, 0x14, 0x8b, 0x54, 0x24, 0x48, 0x0f, 0xb6, 0x3a, 0xc1, 0xe6, 0x08, 0xc1, 0xe0,\
0x08, 0x0b, 0xf7, 0x42, 0x89, 0x54, 0x24, 0x48, 0x8b, 0x14, 0x99, 0x8b, 0xf8, 0xc1, 0xef, 0x0b,\
0x0f, 0xaf, 0xfa, 0x3b, 0xf7, 0x73, 0x15, 0x8b, 0xc7, 0xbf, 0x00, 0x08, 0x00, 0x00, 0x2b, 0xfa,\
0xc1, 0xef, 0x05, 0x03, 0xfa, 0x89, 0x3c, 0x99, 0x03, 0xdb, 0xeb, 0x12, 0x2b, 0xc7, 0x2b, 0xf7,\
0x8b, 0xfa, 0xc1, 0xef, 0x05, 0x2b, 0xd7, 0x89, 0x14, 0x99, 0x8d, 0x5c, 0x1b, 0x01, 0xba, 0x01,\
0x00, 0x00, 0x00, 0x29, 0x54, 0x24, 0x30, 0x75, 0xa4, 0x8b, 0x4c, 0x24, 0x44, 0x8b, 0xfa, 0xd3,\
0xe7, 0x2b, 0xef, 0x03, 0xdd, 0x83, 0x7c, 0x24, 0x10, 0x04, 0x89, 0x5c, 0x24, 0x18, 0x0f, 0x8d,\
0xbb, 0x01, 0x00, 0x00, 0x83, 0x44, 0x24, 0x10, 0x07, 0x83, 0xfb, 0x04, 0x7c, 0x05, 0xbb, 0x03,\
0x00, 0x00, 0x00, 0x8b, 0x4c, 0x24, 0x20, 0xc1, 0xe3, 0x08, 0x8d, 0x9c, 0x0b, 0xc0, 0x06, 0x00,\
0x00, 0xbd, 0x06, 0x00, 0x00, 0x00, 0x8d, 0xa4, 0x24, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,\
0x00, 0x01, 0x73, 0x14, 0x8b, 0x4c, 0x24, 0x48, 0x0f, 0xb6, 0x39, 0xc1, 0xe6, 0x08, 0xc1, 0xe0,\
0x08, 0x0b, 0xf7, 0x41, 0x89, 0x4c, 0x24, 0x48, 0x8b, 0x0c, 0x93, 0x8b, 0xf8, 0xc1, 0xef, 0x0b,\
0x0f, 0xaf, 0xf9, 0x3b, 0xf7, 0x73, 0x15, 0x8b, 0xc7, 0xbf, 0x00, 0x08, 0x00, 0x00, 0x2b, 0xf9,\
0xc1, 0xef, 0x05, 0x03, 0xf9, 0x89, 0x3c, 0x93, 0x03, 0xd2, 0xeb, 0x12, 0x2b, 0xc7, 0x2b, 0xf7,\
0x8b, 0xf9, 0xc1, 0xef, 0x05, 0x2b, 0xcf, 0x89, 0x0c, 0x93, 0x8d, 0x54, 0x12, 0x01, 0x83, 0xed,\
0x01, 0x75, 0xaa, 0x83, 0xea, 0x40, 0x83, 0xfa, 0x04, 0x8b, 0xea, 0x0f, 0x8c, 0xdc, 0x00, 0x00,\
0x00, 0x8b, 0xca, 0xd1, 0xf9, 0x83, 0xe5, 0x01, 0x49, 0x83, 0xcd, 0x02, 0x83, 0xfa, 0x0e, 0x89,\
0x4c, 0x24, 0x30, 0x7d, 0x13, 0xd3, 0xe5, 0x8b, 0xcd, 0x2b, 0xca, 0x8b, 0x54, 0x24, 0x20, 0x8d,\
0x8c, 0x8a, 0xbc, 0x0a, 0x00, 0x00, 0xeb, 0x45, 0x8b, 0x54, 0x24, 0x48, 0x83, 0xe9, 0x04, 0x3d,\
0x00, 0x00, 0x00, 0x01, 0x73, 0x0c, 0x0f, 0xb6, 0x3a, 0xc1, 0xe6, 0x08, 0xc1, 0xe0, 0x08, 0x0b,\
0xf7, 0x42, 0xd1, 0xe8, 0x03, 0xed, 0x3b, 0xf0, 0x72, 0x05, 0x2b, 0xf0, 0x83, 0xcd, 0x01, 0x83,\
0xe9, 0x01, 0x75, 0xdb, 0x8b, 0x4c, 0x24, 0x20, 0x81, 0xc1, 0x88, 0x0c, 0x00, 0x00, 0x89, 0x54,\
0x24, 0x48, 0xc1, 0xe5, 0x04, 0xc7, 0x44, 0x24, 0x30, 0x04, 0x00, 0x00, 0x00, 0xbb, 0x01, 0x00,\
0x00, 0x00, 0x89, 0x5c, 0x24, 0x44, 0x8d, 0xa4, 0x24, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00,\
0x00, 0x01, 0x73, 0x14, 0x8b, 0x54, 0x24, 0x48, 0x0f, 0xb6, 0x3a, 0xc1, 0xe6, 0x08, 0xc1, 0xe0,\
0x08, 0x0b, 0xf7, 0x42, 0x89, 0x54, 0x24, 0x48, 0x8b, 0x14, 0x99, 0x8b, 0xf8, 0xc1, 0xef, 0x0b,\
0x0f, 0xaf, 0xfa, 0x3b, 0xf7, 0x73, 0x15, 0x8b, 0xc7, 0xbf, 0x00, 0x08, 0x00, 0x00, 0x2b, 0xfa,\
0xc1, 0xef, 0x05, 0x03, 0xfa, 0x89, 0x3c, 0x99, 0x03, 0xdb, 0xeb, 0x16, 0x2b, 0xc7, 0x2b, 0xf7,\
0x8b, 0xfa, 0xc1, 0xef, 0x05, 0x2b, 0xd7, 0x0b, 0x6c, 0x24, 0x44, 0x89, 0x14, 0x99, 0x8d, 0x5c,\
0x1b, 0x01, 0xd1, 0x64, 0x24, 0x44, 0x83, 0x6c, 0x24, 0x30, 0x01, 0x75, 0xa0, 0x83, 0xc5, 0x01
};
char p =
{
0xf7, 0x42, 0xd1, 0xe8, 0x03, 0xed, 0x3b, 0xf0, 0x72, 0x05, 0x2b, 0xf0, 0x83, 0xcd, 0x01, 0x83,\
0xe9, 0x01, 0x75, 0xdb, 0x8b, 0x4c, 0x24, 0x20, 0x81, 0xc1, 0x88, 0x0c, 0x00, 0x00, 0x89, 0x54,\
0x24, 0x48, 0xc1, 0xe5, 0x04, 0xc7, 0x44, 0x24, 0x30, 0x04, 0x00, 0x00, 0x00, 0xbb, 0x01, 0x00,\
0x00, 0x00, 0x89, 0x5c, 0x24, 0x44, 0x8d, 0xa4, 0x24, 0x00, 0x00, 0x00, 0x00, 0x3d, 0x00, 0x00
};
int Position = KmpSearch.KmpSearch(s, 0x200, p, 0x40);
if (Position == -1)
cout<<"Data block not found! "<<endl;
else
{
sprintf(szbuf, "Data block found! Position = %08X", Position);
cout<<szbuf<<endl;
}
system("pause");
return 0;
}
膜拜，学习 沙发没了
收藏学习 我只膜拜……以后收藏。 看不懂，只有观望+膜拜！ 看不懂，也要支持一下啦，国庆快乐 不错哦，下载测试，希望楼主搞起X64 KMP，发X64版去{:lol:} 好强悍的789！ 这年头，搜索不用个kmp都不好意思跟人打招呼{:lol:} small-q 发表于 2014-9-29 08:18
不错哦，下载测试，希望楼主搞起X64 KMP，发X64版去
X64还是有点怵。先研究研究你的签名档{:lol:}
页:
[1]
2