算法-用C如何实现高效的字符匹配函数:匹配星号*和点号.

算法-用C如何实现高效的字符匹配函数:匹配星号*和点号.

泛泛之交 发布于 2017-09-13 字数 234 浏览 1420 回复 2

WDK有一个函数FsRtlIsNameInExpression有类似的功能,但是跟我们在命令行上使用的功能不一样的是,星号匹配所有的字符,比如c:windows*.dll,能匹配上c:windowssystem32my.dll,也能匹配上c:windowsmy.dll,而实际上我们的要求是只匹配后者。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

想挽留 2017-11-01 2 楼

如果不想自己写代码分析
有个其他的方式,用windows下的flex
可以生成一个这种匹配的简单词法分析的c代码
嵌入到程序中
:)

清晨说ぺ晚安 2017-10-04 1 楼

老唐,我用汇编实现的。
算法是先逐个字符匹配""号以前的字符串,若不相同则认为不相同,相同则比较下一个字符。遇到""号后从字符串末尾开始向反向逐个字符比较,再次遇到""号则匹配完毕。
这样遇到"
"号从末尾反向比较的方法,加快了算法速度,因为无从知道""号要匹配多少字符。适合你的情况(匹配星号和点号)。
算法只允许输入一个"*"号,也不允许输入其它通配符,比如"?"号,你说的点号是默认运行的,不属于通配符匹配。

// MatchStr.cpp : Defines the entry point for the application.
#include "stdafx.h"

BOOL IsMatch(char *szStr,char *szMatch) //传进来的两个字符串要求以'0'结束
{
BOOL bMatch=TRUE;

_asm
{
pushad
mov ebx,szStr //ebx指向待匹配字符串(路径),edx指向用来匹配的字符串
mov edx,szMatch
cld

fCmp:
mov esi,ebx
lodsb
test al,al
jz over
inc ebx
mov ah,al //ah保存待匹配字符串当前位置的字符

mov esi,edx
lodsb
test al,al
jz over
inc edx

cmp al,'*' //匹配字符串中又匹配符'*'
jz wildCard

cmp ah,al //比较两个字符串中的当前字符是否相同
jz fCmp
jmp notMatch

wildCard:
xor al,al //先计算一次待匹配字符串内容,后面虽会计算但寄存器会有冲突
mov edi,szStr
mov cx,0xFFFF
repnz scasb
not cx
dec cx

mov edi,ebx //先判断待匹配字符串匹配*号内容中是否有'\',有则认为不匹配
sub ebx,szStr
sub ecx,ebx
add ecx,1
mov al,'\'
repnz scasb //前面的ecx中已经保存了字符串长度
jz notMatch

xor al,al
mov edi,szStr //从两个字符串的最后一个字符开始反方向匹配
mov cx,0xFFFF

repnz scasb //获得待匹配字符串长度(不包含结束标志)
not cx
sub cx,2
mov ebx,szStr
add ebx,ecx //让ebx指向最后一个字符

mov edi,szMatch
mov cx,0xFFFF

repnz scasb //获得用来匹配的字符串长度(不包含结束标志)
not cx
sub cx,2
mov edx,szMatch
add edx,ecx //让edx指向最后一个字符

reCmp:
mov esi,ebx
lodsb
test al,al
dec ebx
mov ah,al //ah保存待匹配字符串当前位置的字符

mov esi,edx
lodsb
test al,al
dec edx

cmp al,'*' //反向匹配又到'*'了,说明匹配完毕
jz over

cmp ah,al //比较两个字符串中的当前字符是否相同
jz reCmp
//jmp notMatch

notMatch:
mov bMatch,0
over:
popad
}

return bMatch;
}
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
// TODO: Place code here.
//BOOL bMatch=IsMatch("c:\windows\my.dll","c:\windows*.dll");
//BOOL bMatch=IsMatch("c:\windows\my.dll","c:\windows\*.dll");
//BOOL bMatch=IsMatch("c:\windows\1huang\calc.dll","c:\windows*");
//BOOL bMatch=IsMatch("c:\windows\黄文彬.exe","c:\windows*.dll");
BOOL bMatch=IsMatch("c:\windows黄文彬.dll","c:\windows*.dll");
return 0;
}

代码我测试通过,你这边帮测试下大批量路径时的速度吧,若还想提高速度,可以一次比较4个字符,即lodsd、cmpsd,不过这种需要处理零头的情况,即不满足4个字节的情况。
测试中有任何问题,即时联系我。也期待更好的解法!