JZTXT

2023年11月第三周总结

发布时间 2023-11-19 22:05:27作者: lwj1239

KMP算法

字符串查找算法中的最优解。时间复杂度O(N + M)

下面是自己写的

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define ll long long
#define sc scanf
#define pr printf 
#define N 100 


int kmp(char* p, char* q);
int  pre(char* s, int i);

int main(int argc, char* argv[])
{
	char s[N];
	char s1[N];

	sc("%s", &s);
	//	pr("%s", s);
	getchar();
	sc("%s", &s1);
	//	pr("%s", s1);

	int res = kmp(s, s1);

	pr("%d", res); 

	return 0;
}
int kmp(char* p, char* q)
{
	int len = strlen(q);
	int* next = (int*)malloc(sizeof(int) * len);
	int j = 0;
	int i = 0;

	next[0] = 0;
	next[1] = 0;

	for (i = 2; i < len; i++)
	{
		next[i] = pre(q, i);
	}

	for (int i = 0; i < len; i++)
	{
		pr("%d ", next[i]);
	}
	pr("\n");

	j = 0;
	int nextsetp = next[0];
	/*int res = 0;*/

	while (j < len)
	{
		int k = j;

		for (i = nextsetp; q[i] && p[k] == q[i]; i++, k++)
		{
			;
		}
		if (q[i] == 0) {
			free(next);
			return k - len;
		}
		else if (i != 0){
			nextsetp = next[i];
			/*res = k - next[i];*/
			j = k;
		}
		else {
			j++;
		}
	}

	free(next);

	return -1;
}
int  pre(char* s, int i)
{
	int max = 0;

	for (int j = 0, k = i - 1; j < k && s[j] == s[k]; j++, k--)
	{
		max++;
	}

	return max;
}

下面是一个KMP的模板

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define ll long long
#define sc scanf
#define pr printf 

int kmp(char* p, char* q);
int* getNextArray(char* s);

int main(int argc, char* argv[])
{
	char s[N];
	char s1[N];

	sc("%s", &s);
	//	pr("%s", s);
	getchar();
	sc("%s", &s1);
	//	pr("%s", s1);

	int res = kmp(s, s1);

	pr("%d", res); 

	return 0;
}
int kmp(char* p, char* q)
{
	int q_len = strlen(q);
	int p_len = strlen(p);
	int* next = getNextArray(q);
	int j = 0;
	int i = 0;

	while(i < p_len && j < q_len) {
		 if (p[i] == q[j]) {
		 	i++;
		 	j++; 
		 }
		 else if (j == -1){
		 	i++;
		 }
		 else {
		 	j = next[j];
		 }
	} 
	return j == q_len? i - j:-1;
}
int* getNextArray(char* s)
{
	int len = strlen(s);
	
	if (len == 1)
	{
		int *next = (int*)malloc(sizeof(int) * 1);
		next[0] = -1;
				
		return next;
	}
	
	int *next = (int*)malloc(sizeof(int) * len);
	
	next[0] = -1;
	next[1] = 0;
		
	int i = 2;//next数组的起始计算位置
	int cn = 0;
	
	while(i < len) {
		if (s[i - 1] == s[cn])  {
			next[i++] = ++cn;
		}
		else if (cn > 0){
			cn = next[cn];
		} else {
			next[i++] = 0;
		}
	}
	 
	return next;
}