串的模式匹配

c/c++

浏览数:148

2019-6-29

AD:资源代下载服务

(1)、Brute-Force

  暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。

  如目标串:”caatcat”,t=”cat”,pos=1,匹配过程如图

 程序如下:

#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 100
//顺序串的存储结构,即串中的字符被依次存放在一组连续的存储单元中
typedef struct St
{
	char *ch;	//存放串的起始地址,串中的第i个元素存储在ch[i-1]中
	int length; //串的长度
	int strsize;//分配给串的存储空间大小,若不够,通过realloc()再分配,增加存储空间
}String;

String CreateNullString()
{
	String s;
	s.ch=(char *)malloc(MAXNUM*sizeof(char));	//初始化串的存储空间
	s.length=0;
	s.strsize=MAXNUM;
	return s;
}

//为字符串赋值
void Stringassign(String *s,char s2[])
{
	int i=0;
	//统计串s2的长度,若不够,然后再通过realloc去增加存储空间
	while(s2[i]!='\0')
		i++;
	
	if(i>s->strsize)
	{
		s->ch=(char *)realloc(s->ch,i*sizeof(char));
		s->strsize=i;
	}
	
	s->length=i;
	for(i=0;i<s->length;i++)
		s->ch[i]=s2[i];
	
}

/*
	s:目标字符串
	t:匹配字符串
	pos:索引
  */
int index(String s,String t,int pos)
{
	int i,j;
	if(pos<1 || s.length<pos || s.length-t.length+1<pos)
	{
		printf("输入参数不合理\n");
		exit(0);
	}
	i=pos-1;
	j=0;
	while(i<s.length && j<t.length)
	{
		if(s.ch[i]==t.ch[j])
		{
			i++;	//第i个字符相等,继续匹配
			j++;
		}
		else
		{
			i=i-j+1;	//匹配失败,初始i的后一个位置继续开始匹配
			j=0;
		}
	}
	if(j>=t.length)
		return i-t.length+1;	//匹配成功,返回第匹配成功的字符串的起始地址
	else
		return 0;	//未匹配成功
	
}

void main()
{
	String s,t;
	int i;
	char ch[MAXNUM];
	s=CreateNullString();
	t=CreateNullString();
	printf("请输入主字符串:");
	gets(ch);
	Stringassign(&s,ch);
	printf("输入子串:");
	gets(ch);
	Stringassign(&t,ch);
	printf("输入匹配的起始地址:");
	scanf("%d",&i);
	i=index(s,t,i);
	printf("%d\n",i);
}

运行结果如下:

 备注:关于get()和scanf()函数的区别

gets() : gets从标准输入设备读字符串函数。可以无限读取,不会判断上限,以回车结束读取,所以程序员应该确保buffer的空间足够大,以便在执行读操作时不发生溢出。(从stdio流中读取字符串,直至接受到换行符或EOF时停止,并将读取的结果存放在buffer指针所指向的字符数组中。换行符不作为读取串的内容,读取的换行符被转换为‘\0’空字符,并由此来结束字符串。)

scanf() :它是格式输入函数,即按用户指定的格式从键盘上把数据输入到指定的变量之中。(从标准输入流stdio (标准输入设备,一般指向键盘)中读内容的通用子程序,可以说明的格式读入多个字符,并保存在对应地址的变量中。)

总结:

  scanf( )函数和gets( )函数都可用于输入字符串,但在功能上有区别,gets可以接收空格;而scanf遇到空格、回车和Tab键都会认为输入结束,所以它不能接收空格。

1.scanf()

所在头文件:stdio.h

语法:scanf(“格式控制字符串”,变量地址列表);

接受字符串时:scanf(“%s”,字符数组名或指针);

2.gets()

所在头文件:stdio.h

语法:gets(字符数组名或指针);

3、两者在接受字符串时:

1.不同点:

scanf不能接受空格、制表符Tab、回车等;

而gets能够接受空格、制表符Tab和回车等;

2.相同点:

字符串接受结束后自动加’\0’。

(2)、KMP算法

        最主要的是求模式串的next数组,以字符串str=“ababaaababaa”为例,求解过程如下:

下标 i   0  2  3  4  6  7  8  9  10  11
对应字符   b  b  a  b  a  a
 next[i]  -1  0  0  3  1  2  4  5

 对于上述求解next的过程如下,首先,初始化next[0]=-1,next[1]=0;

当i=2时,比较str[i-1]==str[next[i-1]]。即str[1]=b,str[next[2-1]]=str[0]=a,两者不相等,此时匹配的next已经在无法再向前推了,就取next[2]=0;

当i=3时,比较str[i-1]==str[next[i-1]]。即str[2]=a,str[next[3-1]]=str[0]=a,此时两者相等,则next[i]=next[i]+1,即next[3]=next[2]+1=1;

当i=4时,比较str[i-1]==str[next[i-1]]。即str[3]=b,str[next[4-1]]=str[1]=b,此时两者相等,则next[i]=next[i]+1,即next[3]=next[3]+1=1;

 …

当i=6时,比较str[i-1]==str[next[i-1]]。即str[5]=a,str[next[6-1]]=str[3]=b,此时两者不相等,就继续根据next数组往前查找,求解str[next[next[6-1]]]=str[next[3]]=str[1]=b,此时仍不相等,再继续往前查找,直到查找到next[0]为止,若还不相等,则另next[i]=0;此处,继续查找时str[next[next[next[6-1]]]]=str[next[next[3]]]=str[next[1]]=str[0]=a,此时相等,就会以最后一步匹配的next值为标准进行加1,将值赋予next[i],即str[next[1]]==str[6-1],所以next[i]=next[1]+1=1;

….(后面以此类推)

示例程序

输入

第一行一个整数N,表示测试数据组数。

接下来的N*2行,每两行表示一个测试数据。在每一个测试数据中,第一行为模式串,由不超过10^4个大写字母组成,第二行为原串,由不超过10^6个大写字母组成。

其中N<=20

输出

对于每一个测试数据,按照它们在输入中出现的顺序输出一行Ans,表示模式串在原串中出现的次数。

样例输入:

5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD

样例输出:

3
1
3
1
0

代码如下:

#include <iostream>

using namespace std;

void getNext(const string &str,int *next){
    next[0] = -1;
    int j  = 0, k = -1;
    while(j < str.length()){
        if( k == -1 || str[j] == str[k] ){
            next[++j] = ++k;
        }else{
            k = next[k];
        }
    }
}

int KMP(const string &str1,const string &str2,int next[]){
    int i=0, j=0,count=0;
    while(i < str1.length()){
        int len = str2.length();
        while(j < len && i < str1.length() ){
            if(j == -1 || str1[i] == str2[j]){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        if(j == str2.length()){
            count++;
            j=next[j];
        }
    }
    return count;
}

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        int word=0;
        while(word<n){
            string s1,s2;
            cin>>s1;
            cin>>s2;
            int next[s1.length()]={0},count=0;
            getNext(s1,next);
            for (int i = 0; i < s1.length(); ++i) {
                cout<<next[i]<<" ";
            }
            cout<<endl;
            count=KMP(s2,s1,next);
            cout<<count<<endl;
            word++;
        }
    }
    return 0;
}

 

 

作者:一盏淡酒、醉了夕阳