Module: 前缀函数、Z函数


Problem

2 /10


前缀函数

Theory Click to read/hide

优化前缀函数后（详情请点击此处），我们得到具有 O(n) 渐近性的最终算法：

矢量<int> prefix_function（字符串 s）{
int n = (int ) s.长度();
矢量<int>pi(n);
对于 (int i=1; i<n; ++i) {
int j = pi[i-1< /跨度>];
同时 (j > 0 && s[i] != s[j])
j = pi[j-1];
如果 (s[i] == s[j]) ++j；
pi[i] = j;
}
返回pi;
}

Problem

给定一个非空字符串S，其长度N不超过\(10^6\)。我们假设字符串的元素编号从 1 到 N。
 
对于字符串中 i 字符的每个位置，我们将对在该位置结束并与整个字符串的某个开头匹配的子字符串感兴趣。一般来说，这样的子串会有几个，至少两个。其中最长的长度为i，我们不会对它感兴趣。我们将对剩余的此类子串中最长的感兴趣（请注意，这样的子串始终存在 — 在极端情况下，如果没有找到任何其他子串，则可以使用空子串）。
 
前缀函数\(\pi[i]\)的值将是这个子串的长度。
 
前缀函数用在各种字符串处理算法中。特别是，它可以用来快速解决一个字符串在另一个字符串中出现的问题（“在文本中搜索模式”）。
 
对于从 1 到 N 的所有 i 计算 \(\pi[i ] \).
 
输入
一个长度为N的字符串，\(0 < N <= 10^6\)，由小的拉丁字母组成.
 
输出
输出N个数—每个位置的前缀函数值，以空格分隔。
 

 

例子
<头> <日># <正文>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

输入 输出
1 胡言乱语 0 0 0 1 0 1 0 1 2 3 4