(by flyhigh)
KMP算法是字符串模式匹配算法，可以很大程度上提高匹配速度，关于这个算法及其原理我不多说了，有兴趣的话可以在《数据结构》中找到详细的说明。
但是目前从网上能够找到的算法实现都没有解决DBCS字符集的问题。
举个例子：
主串：唋mcabclmc
模式串：lmc
注：唋=0x86+0x6C,0x6C=’l’
如果你用普通的KMP算法你会找到两个位置：1,7，但事实上只有第7个位置是我们需要的。
通过下面简单的改造我们就可以让它支持中文字符集。
改进后的代码：
NEXT算法不变：void KMP_NEXT(const char *pszPattern,int nSize,int *pNextRecv){ pNextRecv[0]=-1; for(int i=1;i<nSize;i++ ) { int j=pNextRecv[i-1]; while(pszPattern[i]!=pszPattern[j+1]&& j>=0 ) j=pNextRecv[j] ; //递推计算 if(pszPattern[i]==pszPattern[j+1]) pNextRecv[i]=j+1; else pNextRecv[i]=0; // } }
解决这个问题的核心就是在和主串的比较时，一滑过一个单位为一个DBCS字符，看下面的KMP_DBCS算法：//-------------------------------------------------------// 经过多字节字符集过滤处理后的KMP算法//-------------------------------------------------------int KMP_DBCS(const char *pszText,int nPos,const char *pszPattern,int nPatternSize,int *pNext){ int nRet=-1; int bTmpNext=pNext==NULL; if(bTmpNext) { pNext=new int[nPatternSize]; KMP_NEXT(pszPattern,nPatternSize,pNext); } int nLength=strlen(pszText); int i=nPos,j=0; while(i<nLength && nRet==-1) { //计算当前字符长度 int nCharSize=0; if(pszText[i]>0) nCharSize=1; else if(pszText[i+1]<0x40) nCharSize=4; else nCharSize=2; int bMatch=0; if(j+nCharSize<=nPatternSize) bMatch=memcmp(pszText+i,pszPattern+j,nCharSize)==0; if(bMatch) { i+=nCharSize; j+=nCharSize; if(j==nPatternSize) nRet=i-nPatternSize; }else { int nNext=pNext[j]; if(nNext==-1) { i+=nCharSize; j=0; }else { j=nNext; } } } if(bTmpNext) delete []pNext; return nRet;}
上面代码支持GB18030标准。
普通的KMP//-------------------------------------------------------// 普通KMP算法//-------------------------------------------------------int KMP(const char *pszText,int nPos,const char *pszPattern,int nPatternSize,int *pNext){ int nRet=-1; int bTmpNext=pNext==NULL; if(bTmpNext) { pNext=new int[nPatternSize]; KMP_NEXT(pszPattern,nPatternSize,pNext); } int nLength=strlen(pszText); int i=nPos,j=0; while(i<nLength && nRet==-1) { if(pszText[i]==pszPattern[j]) { i++; j++; if(j==nPatternSize) nRet=i-nPatternSize; }else { j=pNext[j]; if(j==-1) i++,j=0; } } if(bTmpNext) delete []pNext; return nRet;}
使用示例：int main(int argc, char *argv[]){ char * s="aba癬ghc_ghabcacabaabc_ghbaab__ghca_gc_g_gb_ghcacab"; char * r=" 0 0 0 0 0"; char * t="_gh"; cout<<s<<endl<<r<<endl; int ps=strlen(t); int *pnext=new int[ps]; KMP_NEXT(t,ps,pnext); cout<<"KMP_DBCS output:"<<endl; int nRet=KMP_DBCS(s,0,t,ps,pnext); int nCount=0; while(nRet!=-1) { cout<<"pos="<<nRet<<endl; nCount++; nRet=KMP_DBCS(s,nRet+ps,t,ps,pnext); } cout<<"count="<<nCount<<endl; cout<<"KMP output"<<endl; nRet=KMP(s,0,t,ps,pnext); nCount=0; while(nRet!=-1) { cout<<"pos="<<nRet<<endl; nCount++; nRet=KMP(s,nRet+ps,t,ps,pnext); } cout<<"count="<<nCount<<endl; delete []pnext; system("PAUSE"); return 0;}
以上代码在VC6中执行通过.
|
[【技术文档】]使KMP算法支持中文字符集