刷题时间：2021/03/26-2021/03/28
数据结构实验之串
一：KMP简单应用
Description
给定两个字符串string1和string2，判断string2是否为string1的子串。
Input
输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。
Output
对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。
Sample
Input
abc
a
123456
45
abc
ddd
Output
1
4
-1
Hint
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char str1[1000002];//串1
char str2[1000002];//串2
int next[1000002];//next数组
int l1,l2;
void Find_next()
{
int i = 0;
int j = -1;
next[0] = -1;//为了后面循环好处理
int len=l2;
while(i < len)
{
if(j == -1 || str2[i] == str2[j])//匹配成功
{
i++;
j++;
next[i] = j;
}
else//不成功退回
j = next[j];
}
}
void kmp()
{
int i = 0, j = 0;
while(i < l1 && j < l2)
{
if(j == -1 || str1[i] == str2[j])
{
i++;
j++;
}
else//不匹配根据next数组移位
j = next[j];
}
if(j == l2)//j走完了，匹配完成
printf("%d\n", i - l2 + 1);//长度=总长度-str2的长度
else
printf("-1\n");
}
int main()
{
while(~scanf("%s", str1))
{
scanf("%s", str2);
l1 = strlen(str1);
l2 = strlen(str2);
Find_next();//找串2的next序列
kmp();
}
return 0;
}
三：KMP应用
Description
有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？
Input
首先输入一个整数n，代表有n个小朋友。下一行输入n个数，分别代表每个小朋友手里糖的数量。
之后再输入一个整数m，代表下面有m个数。下一行输入这m个数。
Output
如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1
Sample
**Input **
5
1 2 3 4 5
3
2 3 4
Output
2 4
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[1000010],b[1000010],nex[1000010];
int n,m;
//定义为全局变量
void Find_next(int b[]) {
int j,k;
k=-1;
j=0;
nex[0]=-1;
while(j<m) {
if(k==-1||b[j]==b[k]){//k==-1很关键，注意体会 {
k++;
j++;
nex[j]=k;
} else {
k=nex[k];
}
}
}
int KMP(int a[],int b[],int z){//注意z的传值 {
Find_next(b);
int i,j;
i=z;
j=0;
while(i<n&&j<m) {
if(j==-1||a[i]==b[j]) {
i++;
j++;
} else j=nex[j];
}
if(j>=m)return i;
//不能为i-m+1;因为当m==0时，返回的为1
return -1;
}
int main() {
int i,t,k;
/*for(i=0;i<n+1;i++)
{
a[i]=b[i]=nex[i]=0;
}*/
memset(a,0,sizeof(a[0]));
memset(b,0,sizeof(b[0]));
memset(nex,0,sizeof(nex[0]));
scanf("%d",&n);
for (i=0; i<n; i++) {
scanf("%d",&a[i]);
}
scanf("%d",&m);
for (i=0; i<m; i++) {
scanf("%d",&b[i]);
}
t=KMP(a,b,0);//第一次kmp从0开始
if(t==-1)printf("-1\n"); else {
k=KMP(a,b,t-m+1);//第二次kmp从t-m+1开始
//两次调用kmp的目的是保证只匹配唯一子串，如有第二个子串则不符合题目要求
if(k==-1){
printf("%d %d",t-m+1,t);
}else {
printf("-1\n");
}
}
return 0;
}
评论区