测试点11 13tle, 不知道怎么解决, 想请教大家
查看原帖
测试点11 13tle, 不知道怎么解决, 想请教大家
253789
Life_format楼主2020/9/23 22:48

最开始直接在函数里用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];			
	}
}
2020/9/23 22:48
加载中...