判断是否是子串（串）

判断是否是子串（串）

时间： 1ms        内存：128M

描述：

设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。

输入：

输入  长度m和n，字符串s和t

输出：

子串所在的位置

示例输入：

5 3
adsff
dsf

示例输出：

2

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<malloc.h>
 
typedef struct
{ 
    int *begin;
	int n;
    int size; 
}LIST; 
  
LIST * init_list(int m) 
{ 
    LIST *p; 
    p=(LIST*)malloc(sizeof(LIST)); 
    if(p!=NULL) 
    { 
        p->begin=(int*)malloc(m*sizeof(int)); 
        if(p->begin!=NULL) 
        { 
            p->n=0; 
            p->size=m; 
            return p; 
        } 
        else
            free(p); 
    } 
    printf("out of space!\n"); 
    return NULL; 
} 
int main()
{
	LIST *p1,*p2;
	int m,n,i,j,t,k;
	char c;
	scanf("%d%d",&m,&n);
	p1=init_list(m);
	p2=init_list(n);
	getchar();
	for(i=0;i<m;i++)
	{
		scanf("%c",&c);
		p1->begin[i]=c;
		p1->n++;
	}
	getchar();
	for(i=0;i<n;i++)
	{
		scanf("%c",&c);
		p2->begin[i]=c;
		p2->n++;
	}
	for(i=0;i<m;i++)
	{
		t=0;
		for(j=i,k=0;j<n+j&&j<m;j++,k++)
		{
			if(p1->begin[j]==p2->begin[k])
				t++;
			else
				break;
		}
		if(t==n)
		{
			printf("%d\n",i+1);
			return 0;
		}
	}
	printf("0\n");
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<malloc.h>
 
typedef struct
{ 
    int *begin;
	int n;
    int size; 
}LIST; 
  
LIST * init_list(int m) 
{ 
    LIST *p; 
    p=(LIST*)malloc(sizeof(LIST)); 
    if(p!=NULL) 
    { 
        p->begin=(int*)malloc(m*sizeof(int)); 
        if(p->begin!=NULL) 
        { 
            p->n=0; 
            p->size=m; 
            return p; 
        } 
        else
            free(p); 
    } 
    printf("out of space!\n"); 
    return NULL; 
} 
int main()
{
	LIST *p1,*p2;
	int m,n,i,j,t,k;
	char c;
	scanf("%d%d",&m,&n);
	p1=init_list(m);
	p2=init_list(n);
	getchar();
	for(i=0;i<m;i++)
	{
		scanf("%c",&c);
		p1->begin[i]=c;
		p1->n++;
	}
	getchar();
	for(i=0;i<n;i++)
	{
		scanf("%c",&c);
		p2->begin[i]=c;
		p2->n++;
	}
	for(i=0;i<m;i++)
	{
		t=0;
		for(j=i,k=0;j<n+j&&j<m;j++,k++)
		{
			if(p1->begin[j]==p2->begin[k])
				t++;
			else
				break;
		}
		if(t==n)
		{
			printf("%d\n",i+1);
			return 0;
		}
	}
	printf("0\n");
	return 0;
}

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