题目描述
KMP字符串
输入样例
3
aba
5
ababa
输出样例
0 2
暴力求解(Time Limit Exceeded)
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main()
{
int lenp, lens;
char p[100050], s[1000050];
scanf("%d", &lenp);
scanf("%s", p);
scanf("%d", &lens);
scanf("%s", s);
for (int i = 0; i <= lens-lenp; i++)
{
int j;
for (j = 0; j < lenp; j++)
{
if (s[i + j] != p[j])
{
break;
}
}
if (j == lenp)
printf("%d ", i);
}
return 0;
}
KMP算法
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int lenp, lens,next[100050];
char p[100050], s[1000050];
int main()
{
scanf("%d", &lenp);
scanf("%s", p);//模板串
scanf("%d", &lens);
scanf("%s", s);//主串
/*求数组next*/
for (int i = 1,j=0; i < lenp; i++) //i是匹配位置,j是匹配长度
{
while (j && p[i] != p[j])
j = next[j - 1];//若不相等,则等于j-1时的长度
if (p[i] == p[j])
j++;//若相等,长度加一
next[i] = j;
}
/*在主串中查询*/
for (int i = 0,j=0; i < lens; i++)
{
while (j && s[i] != p[j])
j = next[j-1];
//若当前不匹配,则next退一位继续匹配
//若j为0,则i+1重新开始
if (s[i] == p[j])
{
j++;//若匹配成功,长度加一
if (j == lenp)//若完全匹配,则输出当前位置
{
printf("%d ", i - lenp + 1);
j = next[lenp - 1];//next退一位继续匹配
}
}
}
return 0;
}