判断是否是子串(串)

判断是否是子串(串)

时间: 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;
}

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

点赞