Ac 로봇 요약

일반적인 예는 N 개의 단어를 준 다음 M 자를 포함하는 문장 한 편을 제공하여 문장 중에 몇 개의 단어가 나타나는지 알아내는 것이다.

AC 로봇을 이해하려면 먼저 패턴 트리 (사전 트리) 트리 및 KMP 패턴 일치 알고리즘에 대한 기본 지식이 있어야 합니다. AC 로봇의 알고리즘은 트리 트리 구성, 실패 포인터 구성 및 패턴 일치 프로세스의 세 단계로 나뉩니다.

KMP 알고리즘을 알고 있다면 KMP 알고리즘의 다음 함수 (시프트 함수 또는 실패 함수) 가 무엇을 하는지 알아야 합니다. KMP 에서는 각각 두 개의 포인터 I 와 J, 그리고 A [I-J+1... I] 와 B [1... J] 를 사용합니다. 즉, I 는 계속 증가하고, j 는 I 가 증가함에 따라 그에 따라 변하며, j 는 a [I] 로 끝나는 길이가 j 인 문자열이 b 문자열의 처음 j 문자와 정확히 일치합니다. A [I+1] ≠ b [j+1] 인 경우 KMP 의 전략은 j 의 위치 (j 값 감소) 를 조정하여 a. 마찬가지로 AC 로봇의 비활성 포인터도 동일합니다