适合做网站背景音乐,学校网站免费html模板,制作网站设计的公司,上海做公益活动有哪些好的网站题目描述 给定两个字符串string1和string2#xff0c;判断string2是否为string1的子串。输入 输入包含多组数据#xff0c;每组测试数据包含两行#xff0c;第一行代表string1(长度小于1000000)#xff0c;第二行代表string2#xff08;长度小于1000000#xff09;#… 题目描述
给定两个字符串string1和string2判断string2是否为string1的子串。输入
输入包含多组数据每组测试数据包含两行第一行代表string1(长度小于1000000)第二行代表string2长度小于1000000string1和string2中保证不出现空格。输出
对于每组输入数据若string2是string1的子串则输出string2在string1中的位置若不是输出-1。示例输入 abc
a
123456
45
abc
ddd示例输出 1
4
-1#include stdio.h
#include stdlib.h
#includestring.h
#define max 1000001
int l1,l2;
int next[1000100];
char s1[1000001],s2[1000001];
void get_next(char s2[],int next[]) //求模式串T的next函数值并存入数组next中
{int i1;next[1]0;int j0;l2strlen(s2);while(il2){if(j0||s2[i]s2[j]){i;j;next[i]j;}elsejnext[j];}
}
void Index_KMP(char s1[],char s2[],int pos)//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
{int i,j;l1strlen(s1);l2strlen(s2);ipos;j1;while(il1-1jl2-1){if(j0||s1[i]s2[j]) //继续比较后续字符{i;j;}elsejnext[j]; //模式串向右移动}if(jl2-1) //匹配成功printf(%d\n,i-l21);else //不成功printf(-1\n);
}
int main()
{while(gets(s1)){gets(s2);l1strlen(s1);l2strlen(s2);get_next(s2,next);Index_KMP(s1,s2,1);}return 0;
}
