判断是否是子串(串)
时间: 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。