나는이 질문에 대답하기에 약간 늦었지만 Z-Algorithm다른 것보다 훨씬 빠르다고 생각 합니다. 최악의 경우 복잡도는 O (m + n)이며 패턴 / 텍스트의 전처리가 필요하지 않습니다. 다른 알고리즘에 비해 코딩이 매우 쉽습니다.

다음과 같은 방식으로 작동합니다.

예를 들어, string이 S ='abaaba'있습니다. 에 대한 z(i)값 을 찾아야 합니다 i=0 to len(S)-1. 설명에 들어가기 전에 먼저 몇 가지 정의를 내려 놓겠습니다.

z(i)= 아니오 접두사의 문자 중 접두사 S와의 접두사가 일치합니다 s(i).

s(i)= ith의 접미사 S.

의 s(i)값 은 다음과 같습니다 s = 'abaaba'.

s(0) = 'abaaba' = S
s(1) = 'baaba'
s(2) = 'aaba'
s(3) = 'aba'
s(4) = 'ba'
s(5) = 'a'

z 값은 각각

z(0) = 6 = length(S)
z(1) = 0
z(2) = 1
z(3) = 3
z(4) = 0
z(5) = 1

알고리즘에 대한 자세한 내용은 다음 링크를 참조하십시오.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

이제 z전처리 오버 헤드없이 모든 값 을 찾는 데 O (N)이 필요합니다. 이 논리를 사용하여 주어진 문자열의 패턴을 어떻게 일치시킬 수 있는지 궁금해 할 것입니다.

예를 들어 봅시다. 패턴 (P) : aba, 문자 (T) : aacbabcabaad.

이것을 P $ T 형식으로 넣으십시오. ( $-패턴이나 텍스트로 표시되지 않는 문자입니다. $잠시 후에 중요 함을 알게 될 것 입니다.)

P$T = aba$aacbabcabaad

우리는 len(P)= 3입니다.

모든 z 값 P$T은

z(0) = 16 = len(P$T)
z(1) = 0
z(2) = 1
z(3) = 0
z(4) = 1
z(5) = 1
z(6) = 0
z(7) = 0
z(8) = 2
z(9) = 0
z(10) = 0
z(11) = 3
z(12) = 0
z(13) = 1
Z(14) = 1
Z(15) = 0

이제 어느 z(i)= len(P). Ans = 11.따라서 패턴은 Ans-len(P)-1=에 7있습니다. -1입니다 $문자.

이제 왜 $그런 특별한 성격이 중요합니까? 고려 P = 'aaa'와 T = 'aaaaaaa'. 특수 문자가 없으면 모두 z(i)증분 값을 갖습니다. 아래 공식을 사용하여 텍스트에서 패턴의 위치를 ​​여전히 찾을 수 있습니다.

조건 : z(i)> = len(P)및 위치 : Ans-len(P). 그러나이 경우의 조건은 약간 까다 롭고 혼란 스럽습니다. 나는 개인적으로 특별한 캐릭터 기술을 선호합니다.

답변