题目

博主博客

题意：

求一个串中相同前后缀长度，并输出

思路：

利用KMP的next数组性质；如果s[next[n-1]]=s[n],则此时前后缀相同，然后再开始回滚，<mark>若s[next[n-1]] == s[n-1]，则子串s[0,1,2,…,next[n-1]]是满足条件的子串</mark>。然后判断s[next[next[n-1]]] == s[n-1]是否成立，这样一直回滚，直到next[next[…next[n-1]]] == -1为止

代码：

#include<stdio.h>
#include<cstring>
#include<stack>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 4e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
char s[maxn];
int nex[maxn];
int len;
void Get_Nex() {
	int j = -1;
	for (int i = 0; i < len; i++) {
		while (s[i] != s[j + 1] && j != -1)j = nex[j];
		if (s[i] == s[j + 1] && i != 0)j++;
			nex[i] = j;
	}
}
stack<int>M;
int main() {
	while (scanf("%s", s) != EOF) {
		len = strlen(s);
		Get_Nex();
		int a = nex[len - 1];
		M.push(len);
		while (a != -1) {
			if (s[a] == s[len - 1]) {
				M.push(a + 1);
				a = nex[a];
			}
		}
		while (!M.empty()) {
			printf("%d ", M.top());
			M.pop();
		}
		puts("");
		//for (int i = 0; i < len; i++)printf("%d ", nex[i]);
	}
	return 0;
}