专栏首页cs串匹配算法

串匹配算法

问题:给定二个字符串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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 计算机二级大题.

    1题 #include <iostream> using namespace std; class MyClass { public: MyClass(...

    东风冷雪
  • c#知识点1.0数据类型

    以前就说,要开始写c#的博客,最近把linux大约写完了,现在开始c#了,java的博客简书一大堆,我就避免撞车吧,其实我是菜鸟(嘻嘻,写不出更好的了) 数据...

    东风冷雪
  • 与算法有关的习题二道

    在猿问上回答了几道题,其中二题还不错,记录一下 题一 要求输入一串不是很长的字符串,在最大的字符后加(max),字符串没有空格,只在第一个出现最大的字符后加(m...

    东风冷雪
  • BZOJ4819: [Sdoi2017]新生舞会(01分数规划)

    Description 学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。有n个男生和n个女生参加舞会 买一个男生和一个女生一起跳舞...

    attack
  • HDU 1213 How Many Tables

    How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

    Angel_Kitty
  • 归并排序

    #include<stdio.h> void MergeArray(int first,int mid,int last,int a[]) { int...

    用户1624346
  • Codeforces 791B Bear and Friendship Condition(DFS,有向图)

    B. Bear and Friendship Condition time limit per test:1 second memory limit per t...

    Angel_Kitty
  • Linux知识之启动外部应用方法

    一般启动外部应用的方法有system,exec与popen。它们功能相似但使用上有所差别。

    Qt君
  • 一张图告诉你为何必须学Python?

    开发岗位的高薪,和互联网的高速发展,吸引了越来越多人加入学习编程的队伍。但是学哪种语言入门?这个问题难倒一大帮选择困难症的人。

    AI科技大本营
  • 亚马逊发布Dash 虚拟按钮SDK,提供一键购物服务

    Dash按钮 是只有拇指大小的硬件设备,将这个按钮贴到商品附近,在手机上进行一次设定后,按下对应的按钮就能轻松进行购买。绿灯亮表示购买成功,红灯亮表示购买失败,...

    BestSDK

扫码关注云+社区

领取腾讯云代金券