CS Academy Prefix Matches

题目链接：https://csacademy.com/contest/archive/task/prefix-matches/

题目大意：给出字符串S，现在规定数列Ai为S中从i开始的字符串的前缀的最大长度，并且该前缀也出现在S的前缀中；数列Bi为S中以i为结尾的字符串的前缀最大长度，该前缀至少从i=2开始，并且该前缀也出现在S的所有前缀中。我们不知道S，但给出A，求B。

解题思路：可以发现，A中出现的每一个都在B中有对应关系。因此针对每个Ai，B中从i开始知道i+Ai的每个位置都对应一个前缀，长度从1递增。又由于长度递增，因此如果Ai，Aj对应B的区间出现重复，那么只需要考虑Ai在重复区间产生的影响即可。

代码：

 1 const int inf = 0x3f3f3f3f;
 2 const int maxn = 1e5 + 5;
 3 int a[maxn], b[maxn];
 4 int n;
 5 
 6 void solve(){
 7     memset(b, 0, sizeof(b));
 8     int i = 2, j = 2;
 9     while(i <= n){
10         if(a[i] != 0){
11             if(j <= i + a[i] - 1){
12                 for(int k = j - i + 1; k <= a[i]; k++){
13                     b[j] = k; j++;
14                 }
15             }
16         }
17         if(j == i) j++;
18         i++;
19         
20     }
21     
22     for(int i = 2; i <= n; i++) {
23         printf("%d", b[i]);
24         if(i != n) printf(" ");
25         else puts("");
26     }
27 }
28 int main(){
29     scanf("%d", &n);
30     memset(a, 0, sizeof(a));
31     for(int i = 2; i <= n; i++) scanf("%d", &a[i]);
32     solve();
33 }

题目：

Prefix Matches

Time limit: 1000 ms
Memory limit: 128 MB

For a string $A_iAi is the size of the longest prefix that can be found again in SS starting at index ii. A_1A1 is not defined.$

On the other hand, $B_iBi is the size of the longest prefix that can be found again in SS ending at index ii. B_iBi is strictly less than ii, B_1B1 is not defined.$

For example, if

You don't know

Standard input

The first line contains a single integer

The second line contains $i^{th}ith number is A_{i+1}Ai+1.$

Standard output

Print $i^{th}ith number is B_{i+1}Bi+1.$

Constraints and notes

$10^52≤N≤105$
It is always possible to generate a string $10^5105.$
It is guaranteed the answer is unique.

Input	Output	Explanation
6 2 1 0 2 1	1 2 0 1 2	A possible string is:
5 4 3 2 1	1 2 3 4
6 0 3 0 1 0	0 1 2 3 0
11 0 1 0 3 0 3 0 2 0 0	0 1 0 1 2 3 2 3 2 0