Module: 접두사 함수, Z 함수

이 문제를 해결하기 위해 일반적인 열거는 작동하지 않습니다. 그것의 점근선은 O(t*s)가 될 것입니다. 따라서 하위 문자열 검색 작업에는 KMP(Knuth-Morris-Pratt) 알고리즘을 사용합니다.
이 알고리즘을 구현하기 위해 문자열 접두사 함수가 사용됩니다. 이것은 길이 n (strong>s 길이)의 숫자 배열이며 각 요소는 최대 길이입니다. 접두사와 일치하는 하위 문자열 s의 가장 큰 자체 접미사입니다. 예:
 

<몸>
O(n^3) 점근법을 사용한 간단한 접두사 함수 알고리즘:


이제 다음 형식의 문자열에 대한 접두사 함수를 만들어야 합니다. & nbsp; t + # + s, 여기서 #은 분명히 텍스트에 없는 구분 문자입니다.  해당 구분 문자 뒤에 접두사 함수의 값을 분석하면 결과 값이 원하는 하위 문자열의 길이와 같으면 해당 항목이 발견된다는 점에 유의해야 합니다. 예를 들어 "abababcab" 문자열의 경우 및 원하는 하위 문자열 "abab", 접두사 기능은 다음과 같습니다.
0 0 1 2 0 1 2 3 4 3 4 0 1 2 해당 문자열 s:
의 요소를 구문 분석해야 합니다. 1 2 3 4 3 4 0 1 2 - 값이 4( 4th 및 6th )인 두 가지 경우가 있습니다. 길이 t,  결과적으로 답을 작성해야 합니다. 4 - 4(길이 t) & nbsp; = 0 및 6 - 4 = 2. 이것이 정답이고 "abab"라는 문자열임을 알 수 있습니다. 실제로 "abababcab" 문자열의 하위 문자열입니다. 위치 0과 2.

 

선	접두사 기능	참고
아바바캡	0 0 1 2 3 4 0 1 2
abcabcd	0 0 0 1 2 3 0
아바아브	0 1 0 1 2 2 3

<헤드> <일># <몸>

입력	출력
1	아바바캡 아밥	0 2

Write the program below
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 0; i < n; ++i) for (int k = 0; k <= i; ++k) if (s.substr(0, k) == s.substr(i - k + 1, k)) pi[i] = k; return pi; } int main() { string s, t; cin >> s >> t; s = t + '#' + s; vector<int> pi; pi = prefix_function(s);
return 0; }