最开始直接在函数里用strlen, 改进了一下依旧11 和13 tle
#include <stdio.h>
#include <stdlib.h>
#include "string.h"
#define N 1000050
void getNext(char *str, int *next);
int kmp(char *P, char *T, int *next, int len2, int len1);
int main(int argc, char *argv[]) {
char str1[N];
char str2[N];
scanf("%s", str1);
scanf("%s", str2);
int next[N];
getNext(str2, next);
int pos = 0;
int old_pos = 0;
int i = 0;
int len2 = strlen(str2);
int len = strlen(str1);
while (old_pos < len) {
int len1 = strlen(&str1[old_pos]);
pos = kmp(&str1[old_pos], str2, next, len2, len1);
if(pos == -1) break;
old_pos += pos + 1;
printf("%d\n", old_pos); //pos is index
}
for(int i = 0; i < len2; i++){
printf("%d ", next[i + 1]);
}
}
int kmp(char *P, char *T, int *next, int len2, int len1)
{
int i = 0;
int j = 0;
while (i < len1 && j < len2) {
if(j == 0 && T[0] != P[i]) i++;
else if(T[j] == P[i]){
if(j == len2 - 1) return i - j;
else j++, i++;
}
else j = next[j];
}
return -1;
}
void getNext(char *str, int *next)
{
int j = 0;
int k = -1;
next[0] = -1;
while(j < strlen(str)){
if(k == -1 || str[j] == str[k]){
next[++j] = ++k;
}
else k = next[k];
}
}