POJ 2752 Seek the Name,Seek the Fame(KMP,前缀与后缀相等)

时间：2022-04-28 07:39:57

Seek the Name,Seek the Fame

过了个年,缓了这么多天终于开始刷题了,好颓废(-.-) 我发现在家真的很难去学习,因为你还要陪父母,干活,做家务等等 但是还是不能浪费时间啊,要利用所有的时间去学习啊

【题目链接】Seek the Name,Seek the Fame

【题目类型】KMP

&题意：

给你一个字符串S。假如为ababcababababcabab 找出这个字符串中所有的前缀等于后缀的子串,输出它们的长度。

第一个为a，最后一个为b，所以1不行。

前两个为ab，最后二个也为ab，所以2行。

前三个为aba，后三个为bab，所以3不行。

以此类推... 找出全部

当然，全部字符串也是可以的。因为ababcababababcabab和ababcababababcabab肯定是一样的。

&题解：

参考:http://blog.csdn.net/niushuai666/article/details/6968507

这道题也是next数组的一个应用。

既然是求模式串匹配，所以要先求出模式串的next数组。这是第一步。

然后我们开始分析怎么用next数组来完成查找前缀后缀的匹配。

我们还是用上面那个字符串为例子来说明一下。

下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

模式串 a b a b c a b a b a b a b c a b a b

next[i] -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9

1）当i = len时，next[len] = next[18] = 9，说明整个字符串前9个字符和后9个字符相同，所以9是满足要求的。

2）next[9] = 4，说明在0-8中前4个字符和后4个字符相同。因为由1）得前9个字符和后9个字符相同，所以，S串的0-3等于5-8，而0-3又等于9-12,5-8又等于14-17，所以结果是0-3等于14-17，即4也是满足题意的。

3）next[4]=2，同2，我们可以得到2也是满足题意的。

4）next[2]=0，表明没有相同的前缀和后缀了，这时，就已经找到了这个S串的所有前缀和后缀。

5）结果就是2,4,9,18.

所以，我们可以推得这样的结论：凡是next[i]！=0的，都是模式串的前缀和后缀相同的字符数。

这也是getnext函数的一个重要应用，多理解理解就可以了。

也就是说nex数组中实在的意义就是前缀有重复的,这题又通过相等的传递性,从前缀通过中间的相等传到最后的后缀,从而解决了问题

【时间复杂度】\(O(m+n)\)

&代码：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const int maxn = 400000 + 9 ;

int nex[maxn],n,ans[maxn];

char s[maxn];

void kmpN(char* x,int len) {

	int i=0,j=nex[0]=-1;

	while(i<len) {

		while(j!=-1&&s[i]!=s[j])j=nex[j];

		nex[++i]=++j;

	}

}

void Solve() {

	while(~scanf("%s",s)) {

		n=strlen(s);

		kmpN(s,n);

		// printf("%s\n", s);

		// rep(i,0,2)printf(" ");

		// rep(i,0,n-1) {

		// 	printf("  %c",s[i] );

		// }

		// PU();

		// rep(i,0,n) {

		// 	printf("%3d",nex[i] );

		// }

		// PU();

		int ct=0;

		int t=n;

		while(t!=0) {

			ans[ct++]=t;

			t=nex[t];

		}

		red(i,ct-1,0) {

			printf("%d%c",ans[i],i==0?'\n':' ');

		}

	}

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("1.in","r",stdin),freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	// int T;cin>>T;while(T--)

	Solve();

	return 0;

}

相关文章