模式匹配的幾種算法（含KMP算法）

 
#include<stdio.h>   
#include<string.h>   
#include<stdlib.h>   
int failure[100];//失配函數   
int strmatch_bf(char *s,char *t)  
{  
    //簡單模式匹配，基本思想：將s和t進行比較，如果相等繼續比較，否則t從頭開始，s從i-j+1開始   
    int i,j;  
    i=j=0;  
    while((i < int(strlen(s))) && (j < int(strlen(t))))  
    {  
        if(s[i]==t[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            i=i-j+1;  
            j=0;  
        }  
    }  
    if(j>=int(strlen(t)))  
        return strlen(s)-i;  
    else  
        return -1;  
}     
int endmatch(char *s,char *t)  
{//先檢測末端標記的模式匹配方法   
      
    int i,j,start=0;  
    int lasts=strlen(s)-1;  
    int lastt=strlen(t)-1;  
    int end=lastt;  
    for(i=0;end<=lasts;end++,start++)  
    {  
        if(s[end]==t[lastt])  
            for(j=0,i=start;j<lastt&&s[i]==t[j];i++,j++);  
            if(j==lastt)  
                return start;//匹配成功   
    }  
    return -1;  
}  
int pmatch_kmp(char *string,char *pat)  
{  
    int i=0,j=0;  
    int lens=strlen(string);  
    int lenp=strlen(pat);  
    while(i<lens&&j<lenp)  
    {  
        if(string[i]==pat[j])  
        {  
            i++;j++;  
        }  
        else  if(j==0)  i++;  
        else j=failure[j-1]+1;    
    }  
    return ((j==lenp)?(i-lenp):-1);  
}  
void fail(char *pat)  
{  
    int n=strlen(pat);  
    int i,j;  
    failure[0]=-1;  
    for(j=1;j<n;j++)  
    {  
        i=failure[j-1];  
        while((pat[j]!=pat[i+1])&&(i>=0))  
            i=failure[i];  
        if(pat[j]==pat[i+1])  
            failure[j]=i+1;  
        else  
            failure[j]=-1;  
    }  
}  
int main()  
{  
    int x;  
    char s[100],t[100];  
    scanf("%s",s);  
    scanf("%s",t);  
    fail(t);  
    x=strmatch_bf(s,t);  
    printf("%d\n",x);  
    x=endmatch(s,t);  
    printf("%d\n",x);  
    x= pmatch_kmp(s,t);  
    printf("%d\n",x);  
    return 0;  
}  

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int failure[100];//失配函數
int strmatch_bf(char *s,char *t)
{
	//簡單模式匹配，基本思想：將s和t進行比較，如果相等繼續比較，否則t從頭開始，s從i-j+1開始
	int i,j;
	i=j=0;
	while((i < int(strlen(s))) && (j < int(strlen(t))))
	{
		if(s[i]==t[j])
		{
			i++;
			j++;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j>=int(strlen(t)))
		return strlen(s)-i;
	else
		return -1;
}	
int endmatch(char *s,char *t)
{//先檢測末端標記的模式匹配方法
	
	int i,j,start=0;
	int lasts=strlen(s)-1;
	int lastt=strlen(t)-1;
	int end=lastt;
	for(i=0;end<=lasts;end++,start++)
	{
		if(s[end]==t[lastt])
			for(j=0,i=start;j<lastt&&s[i]==t[j];i++,j++);
			if(j==lastt)
				return start;//匹配成功
	}
	return -1;
}
int pmatch_kmp(char *string,char *pat)
{
	int i=0,j=0;
	int lens=strlen(string);
	int lenp=strlen(pat);
	while(i<lens&&j<lenp)
	{
		if(string[i]==pat[j])
		{
			i++;j++;
		}
		else  if(j==0)  i++;
		else j=failure[j-1]+1;	
	}
	return ((j==lenp)?(i-lenp):-1);
}
void fail(char *pat)
{
	int n=strlen(pat);
	int i,j;
	failure[0]=-1;
	for(j=1;j<n;j++)
	{
		i=failure[j-1];
		while((pat[j]!=pat[i+1])&&(i>=0))
			i=failure[i];
		if(pat[j]==pat[i+1])
			failure[j]=i+1;
		else
			failure[j]=-1;
	}
}
int main()
{
	int x;
	char s[100],t[100];
	scanf("%s",s);
	scanf("%s",t);
	fail(t);
	x=strmatch_bf(s,t);
	printf("%d\n",x);
	x=endmatch(s,t);
	printf("%d\n",x);
	x= pmatch_kmp(s,t);
	printf("%d\n",x);
    return 0;
}