#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000000
void buildnext(int* next, char* sub) {
next[0] = -1;
int i, j;
for (i = 0,j=-1;i <= strlen(sub) - 1;) {
if (sub[i] == sub[j] || j < 0) {
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
void KMPfinds(char* main,char *sub ) { //kmp算法
int i, j,*next=(int*)malloc(sizeof(int));
buildnext(next, sub);
int k = 0;
for (i = 0,j=i;i <= strlen(main)-1;) {
if (main[i] == sub[j]||j<0) {
j++;
i++;
if (j == strlen(sub)) {
printf("%d\n", i - j+1);
k = 1;
j = next[j-1];
}
continue;
}
else {
j = next[j];
}
}
if (i == strlen(main) &&k==0)
printf("-1");
}
char a[1000000];
int main() {
char* a1 = (char*)malloc(MAXSIZE*sizeof(char)), * a2 = (char*)malloc(MAXSIZE*sizeof(char));
scanf("%s", a1);
scanf("%s", a2); //两个串的初始读入
KMPfinds(a1,a2);
return 0;
}
有什么问题吗
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000000
void buildnext(int* next, char* sub) {
next[0] = -1;
int i, j;
for (i = 0,j=-1;i <= strlen(sub) - 1;) {
if (sub[i] == sub[j] || j < 0) {
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
void KMPfinds(char* main,char *sub ) { //kmp算法
int i, j,*next=(int*)malloc(sizeof(int));
buildnext(next, sub);
int k = 0;
for (i = 0,j=i;i <= strlen(main)-1;) {
if (main[i] == sub[j]||j<0) {
j++;
i++;
if (j == strlen(sub)) {
printf("%d\n", i - j+1);
k = 1;
j = next[j-1];
}
continue;
}
else {
j = next[j];
}
}
if (i == strlen(main) &&k==0)
printf("-1");
}
char a[1000000];
int main() {
char* a1 = (char*)malloc(MAXSIZE*sizeof(char)), * a2 = (char*)malloc(MAXSIZE*sizeof(char));
scanf("%s", a1);
scanf("%s", a2); //两个串的初始读入
KMPfinds(a1,a2);
return 0;
}
有什么问题吗