一种新的字符串匹配算法思路

一开始算导让我学 KMP ,我是拒绝的,因为你不能让我学我就学,这样我是学不好的。后来参照了 Matrix67 的 KMP 算法详解,以及阮一峰的字符串匹配的KMP算法,折腾了三个小时并没有弄明白。于是分析了下数据,自己琢磨出一种基于朴素匹配算法的回溯比对版本。

原理

如,A串ABCDEFG和B串CDE
先用A串的字符’A”B”C'(A[i+p])依次与B串的’C'(B[p])比对,成功后,将a[i+lb-p-1]与b[lb-p-1](字串末端)进行匹配,然后p++,又从A[i+p]开始比对。比对的位置始终从子串的头部->末尾进行回溯,直到计数器 sum 等于字串长度,则退出循环,输出位置。

性能

咱对算法的复杂度并不是太敏感,所以并没有推算出复杂度。不过,进行了一个对长达2144858的A串中寻找一个16位的B串的测试,而为了模拟极端数据环境,故意将B串写在了A串末尾,耗时0.564s。若将 String 改用 char ,换掉 cin、cout 与计时器,在实际运用中是会提速不少的。
本来是想用 KMP 算法做一次效率对比的,但是 HJWJBSR 的 KMP 模板一加载这个2MiB 多的 text.in 就炸了,也就没有测试成功。或许这并不是一个在效率上优于 KMP 的算法,但比朴素算法快到不知道哪里去了,命中率也很高,拿来写一般程序还是可以的Orz

代码

#include "cstdio"
#include "cstring"
#include "cmath"
#include "iostream"
#include "cstdlib"
#include "time.h"
using namespace std;
int main()
{
	clock_t start,finish;
   	double totaltime;
   	start=clock();
	freopen("text.in","r",stdin);
	//A为母串 B为子串
	string a,b;
	cin>>a>>b;
	
	int la = a.length();
	int lb = b.length();

	for (int i = 0; i <= la-lb; i++)
	{
		int p = 0;//当前需匹配
		int sum = 0;//匹配成功计数器
		bool c = true;
		for (int j = 0; j < lb; j++)
		{
			if (c == true)
			{
				//cout<"<"<

后续

葱娘给了个针对性卡算法的input.txt(97.6 KiB)。咱耗时16.984s,欢迎有兴趣的人提供一下 kmp 的结果..

后续的后续

套用刘汝佳的 KMP 跑了一下

#include
#include
#include
#include
#include
#include
#include


void getFail(char* P, int* f)
{
	int m = strlen(P);
	f[0] = 0;
	f[1] = 0;
	for(int i = 1; i < m; i++)
	{
		int j = f[i];
		while(j && P[i] != P[j])
		{
			j = f[j];
		}
		f[i + 1]=P[i]==P[j]?j+1:0;
	}
}

int find(char* T, char*P, int*f)
{
	int n = strlen(T), m = strlen(P);
	getFail(P, f);
	int j = 0;
	for(int i = 0; i < n; i++)
	{
		while(j && P[j] != T[i])
		{
			j = f[j];
		}
		if(P[j] == T[i])
		{
			j++;
		}
		if(j == m)
		{
			return i - m + 1;
		}
	}
	return -1;
}

const int LEN = 1000000;

char s1[LEN] = {'\0'} , s2[LEN] = {'\0'};
int next[LEN] = {'\0'};

int main()
{
	freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	
	scanf("%s%s",s1,s2);
	
	printf("%d",find(s1,s2,next));
	
	fclose(stdin);
	//fclose(stdout);
	return 0;
}

0.3s 过了..我还是去学 KMP 吧

CC BY-SA 4.0 一种新的字符串匹配算法思路 by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论