Luogu p3426 [poi2005]sza-template solution

Luogu P3426 [POI2005]SZA-Template Answer key

Topic link ：P3426 [POI2005]SZA-Template

The question ： You are going to print a string of letters on the paper .

In order to finish the work , You decide to carve a seal . Every time the seal is used , Will put the seal on all Letters are printed on paper .

The same character in the same position can be printed many times . for example ： use aba This seal can be printed ababa The job of （ In the middle of the a It was printed twice ）. however , Because what is printed cannot be erased , It is not allowed to print different characters in the same position . for example ： use aba This seal cannot be printed abcba The job of .

Because it is not easy to carve seals , You want the string length of the seal to be as small as possible .

Enter a length no more than $5\times 10^5$ Non empty string for （ Contains only lowercase letters ）, Represents the characters to be printed on the paper .

Because the seal can be printed at will , That is, there is no order or quantity

So we can consider what kind of situation can continue

Observe the examples

ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba

The front of ababbababbaba Very interesting

It can be found that the leftmost one must be printed once （ crap ）

And the repeated printing is obviously the same as kmp Of border of

notes ： The string $s$ and $0\le r<|s|$ ,

if $s$ The length is $r$ The prefix and length of are $r$ The suffixes of are equal , It's called $s$ The length is $r$ The prefix for is $s$ Of border.

Excerpt from oi-wiki

Consider first finding border, And then use dp Push

set up $f_i$ Indicates printing $s$ Of the $i$ Minimum seal length of prefixes

The upper bound for $f_i=i$

here $f_i$ Under certain conditions, it can be from ${\text{fail}}_i$ Transferred
$$f_i=\{\begin{array}{ll}{f}_{{\text{fail}}_i},& \exists j\ge i-{\text{fail}}_i,f_j=f_{{\text{fail}}_i},\\ & \\ i,& \text{default.}\end{array}$$
The first one looks complicated ,

In fact, that is ababbababbaba such border There is overlap

Just use a bucket for maintenance , Then just move it

Time complexity $O(n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)
char s[N];
int n,fail[N],f[N],h[N];
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s+1); n=strlen(s+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;
    }
    f[1]=1;h[1]=1;
    for(int i=2; i<=n; i++)
    {
    
        f[i]=i;
        if(h[f[fail[i]]]>=i-fail[i])
            f[i]=f[fail[i]];
        h[f[i]]=i;
    }
    cout << f[n] << '\n';
    return 0;
}

Reprint please explain the source