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; 
} 

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