KMP模式匹配 三(串)

KMP模式匹配 三(串)

时间: 1ms        内存:128M

描述:

输入一个主串和一个子串,若匹配成功,则找出匹配的趟数和在子串在主串中的位置,若匹配不成功,则输出0

输入:

输入两个字符串

输出:

输出匹配的趟数和位置

示例输入:

ababcabcacbab
abcac

示例输出:

3 6

提示:

参考答案(内存最优[752]):

#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
  
int index(char s[],char t[],int pos) 
{ 
    int i,j,slen,tlen; 
    i=pos; 
    j=0;  
    slen=strlen(s); 
    tlen=strlen(t);  
    while(i<slen && j<tlen) 
    { 
          if(s[i]==t[j]) { 
             i++;j++; 
          } 
          else{ 
              i=i-j+1; 
              j=0; 
          } 
    } 
    if(j>=tlen)  
        return i-tlen+1; 
    return -1; 
} 
  
  
int main() 
{ 
    char s[80],t[80]; 
    int i=0,pos=0,flag=0,count=0; 
    gets(s); 
    gets(t); 
    flag=index(s,t,pos); 
    if(flag==-1) 
        printf("0\n"); 
    else{
	     for(i=0;i<flag;i++)
			 if(s[i]==t[0])
				 count++;
	}
	printf("%d %d\n",count,flag);
    return 0; 
} 

参考答案(时间最优[0]):

#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
  
int index(char s[],char t[],int pos) 
{ 
    int i,j,slen,tlen; 
    i=pos; 
    j=0;  
    slen=strlen(s); 
    tlen=strlen(t);  
    while(i<slen && j<tlen) 
    { 
          if(s[i]==t[j]) { 
             i++;j++; 
          } 
          else{ 
              i=i-j+1; 
              j=0; 
          } 
    } 
    if(j>=tlen)  
        return i-tlen+1; 
    return -1; 
} 
  
  
int main() 
{ 
    char s[80],t[80]; 
    int i=0,pos=0,flag=0,count=0; 
    gets(s); 
    gets(t); 
    flag=index(s,t,pos); 
    if(flag==-1) 
        printf("0\n"); 
    else{
	     for(i=0;i<flag;i++)
			 if(s[i]==t[0])
				 count++;
	}
	printf("%d %d\n",count,flag);
    return 0; 
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞