用kmp算法,最后三个超时,怎么优化
查看原帖
用kmp算法,最后三个超时,怎么优化
689878
XTH1111楼主2022/4/8 22:41
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<assert.h>
#include <ctype.h>
void Getnext(char* str2, int* next, int lenstr2)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int k = 0;
	while (i < lenstr2)
	{
		if (k == -1 || (next[i - 1] == next[k]))
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
			k = next[k];//回溯
	}


}
int KMP(char* str1, char* str2, int pos)
{
	assert(str1 && str2);
	int lenstr1 = strlen(str1);
	int lenstr2 = strlen(str2);
	if (lenstr1 == 0 || lenstr2 == 0) return -1;
	if (pos<0 || pos>lenstr1) return -1;
	int i = pos;
	int j = 0;
	int* next = (int*)malloc(sizeof(int) * lenstr2);
	assert(next != NULL);
	Getnext(str2, next, lenstr2);
	while (i < lenstr1 && j < lenstr2)
	{
		if (j == -1 || str1[i] == str2[j])
		{

			i++;
			j++;
		}
		else
			j = next[j]; //平移子串,从新判断
		if (j >= lenstr2)
			return i - j;
	}
	return -1;

}
int main()
{
	char arr1[1000000] = { 0 };
	char arr2[11] = { 0 };
	int count = 0;
	scanf("%s", arr2);
	getchar();
	for (int i = 0; i < sizeof(arr1); i++)
	{
		scanf("%c", &arr1[i]);
		if (arr1[i] == '\n')
		{
			arr1[i] = '\0';
			break;
		}
	}
	for (int i = 0; i < strlen(arr1); i++)
		arr1[i] = toupper(arr1[i]);
	for (int i = 0; i < strlen(arr2); i++)
		arr2[i] = toupper(arr2[i]);
	int str = KMP(arr1, arr2, 0);
	int k = 0;
	int t = 1;
	if (str != -1)
	{
		if (arr1[str - 1] == ' ' && arr1[str + strlen(arr2)] == ' ')
		{
			if (t)
			{
				k = str;
				t=t - 1;
			}
			count++;

		}

		if (str == 0 && arr1[strlen(arr2)] == ' ')
		{
			if (t)
			{
				k = str;
				t=t - 1;
			}
			count++;
		}
	}

	while (1)
	{
		str = KMP(arr1, arr2, str + 1);
		if (str != -1)
		{
			if (arr1[str - 1] == ' ' && arr1[str + strlen(arr2)] == ' ')
			{
				if (t)
				{
					k = str;
					t=t - 1;
				}
				count++;
			}
		}
		else
			break;
		if ((str == strlen(arr1) - strlen(arr2)) && arr1[str - 1] == ' ')
		{
			if (t)
			{
				k = str;
				t=t - 1;
			}
			count++;
		}
		if (str > strlen(arr1))
			break;
	}
	if (count != 0)
		printf("%d %d", count, k);
	else
		printf("%d", count - 1);
	return 0;
}
2022/4/8 22:41
加载中...