2.Periodicity (POI: 18 - solved: 68)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I appreciate if anyone can help me share his good problems of POIs, just list them in the comments and I'll check them all.

Link

Given a string S of size n. We define $\text{[math]}$ as follows:

$\text{[math]}$

In other hand, $\text{[math]}$ is a set of sizes of periods A such that S = AAA...AB(B is a prefix of A).

Now, we want to create the minimum lexicographically string C of size n such that $\text{[math]}$ .

There are k such tests.

1 ≤ k ≤ 20, 1 ≤ n ≤ 250000

________________
3
ABIABUABIAB
BABBAB
BABURBAB
________________
01001101001
010010
01000010
________________

Some of hints only make a good look and may not solve the problem. When you look in that way, you'll come close to the solution. And if you didn't look in that way, you won't get the next hints and you'll get confused in 13 spoilers.

hint1

hint2

Some problem just used this idea : 526D - Om Nom and Necklace

hint3

hint4

You may have a sense of recursive solving the problem as you see we almost minimized the problem in the minimum period. I agree with you, but see more carefully.

Let's see a period as a suffix which is equal to a prefix of S, what we saw in hint 1.

Tell me if you come up with a easier and shorter answer, I'll become glad.

Code

//    whoisHussain.org
#include <bits/stdc++.h>
using namespace std;

const int N = 300011;
int f[N],q, g[N],sz; 
bool a[N];
int32_t main(){
        string s;
        int n;
        ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
        cin >> q;
        while( q-- ){
                cin >> s;
                n = s.size(), sz = 0;

                f[0] = f[1] = 0;
                for(int i = 2,j = 0; i <= n; i++){
                        while( j!=0 && s[i-1] != s[j] )
                                j = f[j]; 
                        if( s[i-1]==s[j] ) j++;
                        f[i] = j;
                }

                for(int i = n; i; i = f[i] ) g[sz++] = n-i;
                
                for(int i = sz-1, gg = n, cz = 0;i>-1; cz = gg-g[i], gg = g[i], i--){ 
                        for(int j = 0; j < min(gg-g[i], n-gg); j++) a[ j + g[i] ] = a[ j + gg ];
                        if( gg - g[i] > n - gg && (cz == 0 || (gg - g[i]) % cz == 0) ){ 
                                int j = 0;
                                for(; j < cz; j++)
                                        if( a[j + gg-cz ] != a[ gg + j ] ) break;
                                if( j == cz ) a[gg - 1] = 1 - a[gg + cz - 1]; 
                        }
                        a[g[i]] = 0;
                }
                for(int i = 0; i < n; i++)
                        printf("%d",a[i]),a[i] = 0;
                printf("\n");
        }
}

Hope you enjoy the problem :) and it helped you.

saliii's blog