Module: 접두사 함수, Z 함수


Problem

2 /10


접두사 기능

Theory Click to read/hide

접두사 기능을 최적화한 후(자세한 내용은 여기) O(n) 점근법을 사용하여 최종 알고리즘을 얻습니다.

벡터<정수> 접두사_함수(문자열 s) {
정수 n = (정수 ) s.길이();
벡터<정수>파이(n);
for (int i=1; i<n; ++i) {
int j = pi[i-1< /스팬>];
동안 (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
파이[i] = j;
}
리턴파이;
}

Problem

길이 N이 \(10^6\)S가 주어진 경우 >. 문자열의 요소는 1에서 N까지 번호가 매겨져 있다고 가정합니다.
 
문자열에서 i 문자의 각 위치에 대해 해당 위치에서 끝나고 전체 문자열의 일부 시작 부분과 일치하는 하위 문자열에 관심이 있습니다. 일반적으로 말하자면, 이러한 하위 문자열은 여러 개, 적어도 두 개 있을 것입니다. 가장 긴 것의 길이는 i이므로 관심이 없습니다. 그리고 나머지 부분 문자열 중 가장 긴 부분 문자열에 관심을 가질 것입니다(그러한 부분 문자열은 항상 존재한다는 점에 유의하십시오. 극단적인 경우 다른 항목이 없으면 빈 부분 문자열이 됩니다).
 
접두사 함수 \(\pi[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