KMP字符串匹配模板洛谷 P3375

题意

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）

样例：

输入

ABABABC

ABA

输出

1

3

0 0 1

解题思路

当然是使用KMP啦，只不过这个要求比较高一些。

注意这里要输出的next数组内容是不能进行优化的那种，否者就会WA，带有优化的可以看第一个代码。

详情见代码。这个也可以算作一个模板了。

代码实现

//这个是对next进行的优化

void getnext()               //做的第一步是获得next【】的值

{

	int i=0,k=-1;

	next[0]=-1;

	while(i<lenb)

	{

		if(k==-1)//这里和平常的有些不同，这里进行了一些优化，将两个条件分开了。

		{

			next[++i]=++k;

			continue;

		}

		if (b[i]==b[k])

		{

			if(b[i+1]==b[k+1]) //这里进行了优化，一般介绍KMP的文章中都有会这个。

				next[++i]=next[++k];

			else

				next[++i]=++k;

		}

		else k=next[k];

	}

}

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=1e6+7;

char a[maxn],b[maxn];

int next[maxn];

int lena, lenb;

void getnext()               //做的第一步是获得next【】的值

{

	int i=0,k=-1;

	next[0]=-1;

	while(i<lenb)

	{

		if (k==-1 || b[i]==b[k])

			next[++i]=++k;

		else k=next[k];

	}

}

void KMP()

{

	getnext();

	int i=0,j=0,cnt=0;

	while (i<lena)

	{

		if (j==-1||a[i]==b[j])

		{

			i++;j++;

		}

		else j=next[j];

		if (j==lenb)

		{

			printf("%d\n", i-j+1);

			j=next[j];

		}

	}

}

int main()

{

	while(scanf("%s",a)!=EOF)

	{

		scanf("%s",b);

		lena=strlen(a);

		lenb=strlen(b);

		KMP();

		for(int i=1; i<=lenb; i++)

		{

			printf("%d ", next[i]);

		}

		printf("\n");

	}

	return 0;

}

巴特西

KMP字符串匹配模板洛谷 P3375

KMP字符串匹配模板洛谷 P3375

题意

解题思路

代码实现

最新文章

热门文章

巴特西

KMP字符串匹配 模板 洛谷 P3375

KMP字符串匹配 模板 洛谷 P3375

题意

解题思路

代码实现

最新文章

热门文章

KMP字符串匹配模板洛谷 P3375

KMP字符串匹配模板洛谷 P3375