AC 자동 동기 (다 중 모드 일치)
주요 3 단계: trie 트 리 구축, 실패 포인터 구축, 일치 하 는 갯 수 찾기
트 리: 사전 트 리, 단어 찾기 트 리 라 고도 부 르 며 트 리 구조 로 대량의 문자열 을 저장 하 는 데 사 용 됩 니 다.문자열 의 공공 접 두 사 를 이용 하여 저장 공간 을 절약 하 는 것 이 장점 이다.
구체 적 인 참조:http://www.cppblog.com/abilitytao/archive/2009/04/21/80598.aspx
실패 포인터: KMP 에 작용 하 는 next [] 는 유사 하지만 실제 적 으로 다 릅 니 다. 문자열 s [nMax], k = next [i] 에 대해 서 는 s [i] = s [k] 를 구하 지 말고 앞의 k - 1 글자 만 같 으 면 됩 니 다.실패 노드 는 두 노드 가 같 아야 할 뿐만 아니 라 앞의 k - 1 노드 도 같 아야 한다.이것 은 next 작용 과 의 차이 이다.
필요 한 데이터 구조:
struct Node
{
Node *fail;
Node *next[Max];
int count;
Node()
{
fail = NULL;
memset(next, 0, sizeof(next));
count = 0;
}
}*queue[nMax];
char keyWord[mMax];
char str[nMax];
int ans;
알고리즘 템 플 릿:
void insert(char s[], Node *root)
// tire , ,
{
Node *p = root;
for(int i = 0; s[i]; ++ i)
{
int index = s[i] - 'a';
if(p->next[index] == NULL) p->next[index] = new Node();
p = p->next[index];
}
p ->count ++;
}
void buildFailNode(Node *root)
// ,
{
int front = 0,
rear = 0;
queue[front ++] = root;
while(rear < front)
{
Node *p = queue[rear ++];
for(int i = 0; i < Max; ++ i)
{
if(p->next[i])
{
Node *fa = p->fail;
while(fa != NULL)// p fa i
{
if(fa->next[i])
{
p->next[i]->fail = fa->next[i];
break;
}
fa = fa->fail;
}
if(fa == NULL) p->next[i]->fail = root;
queue[front ++] = p->next[i];
}
}
}
}
void match(Node *root)
// , 。
{
Node *p = root;
for(int i = 0; str[i]; ++ i)
{
int index = str[i] - 'a';
while(p->next[index] == NULL && p != root)
p = p->fail;
p = p->next[index];
p = (p == NULL) ? root : p;// while() p != root
Node *_p = p;// p _p,p ,p
while(_p != root && _p->count != -1)
// while str[i]
{
ans += _p->count;
_p->count = -1;
_p = _p ->fail;
}
}
}
상세 한 참조, 그림 과 글 이 모두 훌륭 하 다.http://www.cppblog.com/mythit/archive/2009/04/21/80633.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.