串匹配算法

问题：给定二个字符串S和T,在主串S中查找子串T的过程称之为字符串匹配问题（string matching,也称之为模式匹配)。在文本处理系统，操作系统，编译系统，数据库系统以及internet信息检索中，串匹配是使用最频繁操作。

有蛮力法，即BF(暴力匹配算法，和KMP算法。

我只会bf算法，kmp还是有问题。

思路

从主串S开始的一个字符串和子串T的第一个字符串进行比较，若相等，则比较二者的后续字符；若不相等，则主串S的第二个字符和子串T的第一个字符进行比较，重复上述过程，若T中的字符全部匹配完，则说明本次匹配成功，若S中字符全部比较完毕，则匹配失败。

#include<iostream>
#include<time.h>
using namespace std;
int  bfstring(char k[],char s[]);
int main()
{

    char k[]="abcabcacb";
    char s[]="abcac";

    clock_t start,finish;
        int index;

double duration;

start= clock();

for(int z=0; z<1000000; z++)   //扩大匹配时间
{


 index=bfstring(k,s);


}

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC;

printf("time=%lf seconds\n",duration);


    if(index==0)
  cout<<"匹配失败"<<endl;
    else
  cout<<"本次匹配的开始位置:"<<index<<endl;

return 0;
}

//k为主串，S为字串。
int  bfstring(char k[],char s[])
{
    int i=0,j=0;
    int index=0;
   while(k[i]!='\0'&&s[j]!='\0')    
   {
       
        if(k[i]==s[j])
        {
            i++;
            j++;
        }
        else{
         index++;
         j=0;    
         i=index;
        }

   }

   if(s[j]=='\0')
    return index+1;  //返回本次匹配的开始位置。
   return 0;

}

结果

time=0.074000 seconds
本次匹配的开始位置:4
Press any key to continue

---

kmp算法。

主要是寻找next的值。

#include<iostream>
#include<time.h>
using namespace std;
int  kmp(char k[],char s[]);
void getNext(char s[],int next[]);
int main()
{

    char k[]="abcabcacb";
    char s[]="abcac";

    clock_t start,finish;
        int index;

double duration;

start= clock();

for(int z=0; z<1000000; z++)   //扩大匹配时间
{


 index=kmp(k,s);


}

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC;

printf("time=%lf seconds\n",duration);


    if(index==0)
  cout<<"匹配失败"<<endl;
    else
  cout<<"本次匹配的开始位置:"<<index<<endl;

return 0;
}

//k为主串，S为字串。
int  kmp(char k[],char s[])
{
    int i=0,j=0;
    int next[100];
    getNext(s,next);
   while(k[i]!='\0'&&s[j]!='\0')    
   {
       
        if(k[i]==s[j])
        {
            i++;
            j++;
        }
        else{
         j=next[j];
         if(j==-1)
         {
          i++;
          j++;  
         }
        }
   }

   if(s[j]=='\0')
    return i-strlen(s)+1;  //返回本次匹配的开始位置。
   return 0;

}

void getNext(char s[],int next[])
{

 int i,j,len;
 next[0]=-1;
 for(j=1; s[j]!='\0'; j++)  //依次求next[j]
 {
       // 相等的子串最大长度为j-1
  for(len=j-1; len>=1; len--) 
  {
     //依次比较 S[0]~S[len-1]与S[j-len]~s[j-1]
      for(i=0; i<len; i++) 
    if(s[i]!=s[j-len+i])  
        break;
    if(i==len)
    {
        next[j]=len;
        break;
    }


  }

 if(len<1)  //其它情况无相等字符串
 next[j]=0;

 }

}

结果

time=0.135000 seconds
本次匹配的开始位置:4
Press any key to continue