一个基于KMP优化算法的数据块匹配算法类

lucky_789 · 发表于 2014-9-28 21:52:08

本帖最后由 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[PYG] */
/* 说明: 修改自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[PYG] */
/* 说明: 修改自July的KMP优化算法 */
/********************************************************************/
#include "KmpSearchData.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
KmpSearchData::KmpSearchData()
{
}
KmpSearchData::~KmpSearchData()
{
}
/**************************************************************************/
/* 函数名称: KmpSearch */
/* 函数作者: lucky_789[PYG] */
/* 函数参数: 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[pSize];
memset(next, 0, pSize * sizeof(int));
GetNext(p, pSize, next);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
delete next;
if (j == pLen)
return i - j;
else
return -1;
}
/**************************************************************************/
/* 函数名称: GetNext */
/* 函数作者: lucky_789[PYG] */
/* 函数参数: p: 查找的模式数据块(在s中查找p的位置) */
/* pSize:查找的模式数据块大小(字节数) */
/* next: 优化过后的next数组 */
/**************************************************************************/
void KmpSearchData::GetNext(char *p, int pSize, int next[])
{
int pLen = pSize;
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}

复制代码

#include <iOStream>
#include "KmpSearchData.h"
using namespace std;
KmpSearchData KmpSearch;
int main()
{
char szbuf[MAX_PATH] = {0};
char s[0x200] =
{
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[0x40] =
{
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;
}

复制代码

goushibee · 发表于 2014-9-28 22:08:03

膜拜，学习

wgz001 · 发表于 2014-9-28 22:12:42

沙发没了
收藏学习

vipcrack · 发表于 2014-9-28 22:17:27

我只膜拜……以后收藏。

pentium450 · 发表于 2014-9-28 22:31:54

看不懂，只有观望+膜拜！

cfc1680 · 发表于 2014-9-29 08:11:04

看不懂，也要支持一下啦，国庆快乐

small-q · 发表于 2014-9-29 08:18:32

不错哦，下载测试，希望楼主搞起X64 KMP，发X64版去

GGLHY · 发表于 2014-9-29 08:55:22

好强悍的789！

zaas · 发表于 2014-9-29 11:11:43

这年头，搜索不用个kmp都不好意思跟人打招呼

lucky_789 · 发表于 2014-9-29 12:36:15

small-q 发表于 2014-9-29 08:18
不错哦，下载测试，希望楼主搞起X64 KMP，发X64版去

X64还是有点怵。先研究研究你的签名档

		自动登录	找回密码
密码			加入我们

一个基于KMP优化算法的数据块匹配算法类

评分

点评

点评