[Luogu p3426] SZA template (string) (KMP)

SZA-Template

Topic link ：luogu P3426

The main idea of the topic

Give you a string , Then you can choose a string to generate it .
Each time you can put a string of your choice onto the current string , Then if the following paragraph is the same as the previous paragraph , Then you can overlap .
（ That is, a character in one position can appear many times , But different characters cannot appear ）
Then how short is the shortest string you can use .

Ideas

First of all, an obvious thing is that the satisfied string is at least string Border.
Then consider what one Border Can only be , That's it fail From the tree $n$ The adjacent points on the path of must be able to be found .

As for how to see if it can be made up , That is the current string, which goes to the next string , It must be at least as long as Xinduo （ That is, you can get a new one by two ）, As for why this is Border Definition , Just think about it .

What do you think , We consider the dfs, Every time I come to Border Click to delete other brothers , Then the linked list maintains the middle distance , Then delete yourself and update the gap size every time you go to your son , That is, the gap size should be less than or equal to the length of the point you want to see .

Code

#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int N = 5e5 + 100;
char s[N];
int n, l[N], r[N], fail[N], ans, gap;
bool sp[N];
vector <int> G[N];

void del(int now) {
    
	r[l[now]] = r[now];
	l[r[now]] = l[now];
}

void dfs(int now) {
    
	if (sp[now] && now >= gap) {
    
		ans = min(ans, now);
	}
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (sp[x]) continue;
		dfs(x);
	}
	if (l[now] && r[now] != n + 1) {
    
		gap = max(gap, r[now] - l[now]);
	}
	del(now);
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (!sp[x]) continue;
		dfs(x);
	}
}

int main() {
    
	scanf("%s", s + 1); n = strlen(s + 1);
	
	ans = n;
	G[0].push_back(1);
	for (int i = 2, j = 0; i <= n; i++) {
    
		while (j && s[i] != s[j + 1]) j = fail[j];
		if (s[i] == s[j + 1]) j++; fail[i] = j; G[j].push_back(i);
	}
	
	int now = n; while (now) sp[now] = 1, now = fail[now];
	for (int i = 1; i <= n; i++) l[i] = i - 1, r[i] = i + 1;
	
	gap = 1;
	dfs(0);
	
	printf("%d", ans);
	
	return 0;
}