알고리즘 서론 - AC 자동 동기

화전 북풍 취 일자: 2016 - 05 - 03
AC 자동 동 기 는 비교적 효율 적 인 다 중 모드 매 칭 알고리즘 이다.KMP 가 패턴 문자열 에 있 는 상태 이동 알고리즘 과 유사 합 니 다. AC 자동 동 기 는 trie 트 리 에 상태 이동 을 만들어 서 일치 하 는 문자열 을 한 번 훑 어보 면 모든 패턴 문자열 을 찾 을 수 있 습 니 다.AC 자동 동 기 는 일반적으로 다음 과 같은 세 가지 단계 가 있다. 우선, 모든 패턴 문자열 에 trie 트 리 를 만든다.그 다음 에 trie 트 리 의 모든 노드 에 대해 가장 긴 접미사 에 대응 하 는 접두사 문자열 을 포인터 로 하여 AC 자동 동 기 를 만 듭 니 다.마지막 단 계 는 AC 자동 동기 에 텍스트 문자열 을 일치 시 킵 니 다.
제목 링크:http://hihocoder.com/problemset/problem/1036?sid=786758
참조 코드:

#include <iostream>
#include <queue>
#include <string>
#include <string.h>
using namespace std;

#define size 26

struct node
{
    node *fail;          //    
    node *next[size];    //Tire     26    ,    26     
    int count;           //             
    node()
    {
        fail = NULL;
        count = 0;
        memset(next, NULL, sizeof(next));
    }
};

void Insert(node *root, string str)
{
    node *p = root;
    int i = 0, index;
    for (int i = 0; i < str.length(); i++)
    {
        index = str[i] - 'a';
        if (p->next[index] == NULL)
            p->next[index] = new node();
        p = p->next[index];
    }
    p->count++;
}
void GetFail(node *root)
{
    int i;
    root->fail = NULL;
    queue<node*> q;
    q.push(root);
    while (q.empty() == false)
    {
        node *temp = q.front();
        q.pop();
        node *p = NULL;
        for (i = 0; i<size; i++)
        {
            if (temp->next[i] != NULL)
            {
                if (temp == root)
                    temp->next[i]->fail = root;
                else
                {
                    p = temp->fail;
                    while (p != NULL)
                    {
                        if (p->next[i] != NULL)
                        {
                            temp->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL)
                        temp->next[i]->fail = root;
                }
                q.push(temp->next[i]);
            }
        }
    }
}
bool Query(node *root, string str)
{
    int cnt = 0, index;
    node *p = root;
    for (int i = 0; i < str.length(); i++)
    {
        index = str[i] - 'a';
        while (p->next[index] == NULL && p != root)
            p = p->fail;
        p = p->next[index];
        p = (p == NULL) ? root : p;
        node *temp = p;
        while (temp != root)
        {
            if (temp->count != 0)
                return true;
            else
                temp = temp->fail;
        }
    }
    return false;
}
int main()
{
    int n;
    node *root = new node();
    cin >> n;
    string keyword;
    while (n--)
    {
        cin >> keyword;
        Insert(root, keyword);
    }
    GetFail(root);
    string str;
    cin >> str;
    if (Query(root, str))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

위의 코드 는 이론 적 으로 정확 한 코드 이지 만 이것 을 제출 하면 시간 이 초과 되 고 84 줄 while 를 if 로 수정 하면 통과 할 수 있 지만 수정 후 논리 적 으로 잘못된 코드 입 니 다.
다음은 AC 자동 동기 기능 확장 코드 를 드 립 니 다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <fstream>
using namespace std;

#define size 26

struct ACNode
{
    ACNode *fail;          //    
    ACNode *next[size];    //Tire     26    ,    26     
    int count;             //             ,            
    int patternNo;         //         ，           
    ACNode()
    {
        fail = NULL;
        count = 0;
        patternNo = -1;
        memset(next, NULL, sizeof(next));
    }
};
void Insert(ACNode *root, string str, int patterNo)
{
    ACNode *p = root;
    int i = 0, index;
    for (int i = 0; i < str.length(); i++)
    {
        index = str[i] - 'a';
        if (p->next[index] == NULL)
            p->next[index] = new ACNode();
        p = p->next[index];
    }
    p->count++;
    p->patternNo = patterNo;
}
void GetFail(ACNode *root)
{
    int i;
    root->fail = NULL;
    queue<ACNode*> q;
    q.push(root);
    while (q.empty() == false)
    {
        ACNode *temp = q.front();
        q.pop();
        ACNode *p = NULL;
        for (i = 0; i<size; i++)
        {
            if (temp->next[i] != NULL)
            {
                if (temp == root)
                    temp->next[i]->fail = root;
                else
                {
                    p = temp->fail;
                    while (p != NULL)
                    {
                        if (p->next[i] != NULL)
                        {
                            temp->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL)
                        temp->next[i]->fail = root;
                }
                q.push(temp->next[i]);
            }
        }
    }
}
int Query(ACNode *root, string str, vector<string> &keySet)
{
    int cnt = 0, index;
    ACNode *p = root;
    for (int i = 0; i < str.length();i++)
    {
        index = str[i] - 'a';
        while (p->next[index] == NULL && p != root)
            p = p->fail;
        p = p->next[index];
        p = (p == NULL) ? root : p;
        ACNode *temp = p;
        while (temp != root)
        {
            if (temp->count>0)
            {
                int patternNo = temp->patternNo;
                int patternLength = keySet[patternNo].length();
                cout << i - patternLength + 1 << " " << keySet[patternNo] << endl;
                cnt += temp->count;
            }
            temp = temp->fail;
        }
    }
    return cnt;
}
int main()
{
    ifstream in(".\\input.txt");
    cin.rdbuf(in.rdbuf());

    int n;
    ACNode *root = new ACNode();
    cin >> n;
    string keyword;
    vector<string> keySet;
    for (int i = 0; i < n;i++)
    {
        cin >> keyword;
        keySet.push_back(keyword);
        Insert(root, keyword,i);
    }
    GetFail(root);
    string str;
    cin >> str;
    Query(root, str, keySet);
    return 0;
}

참고 블 로그:http://www.cppblog.com/mythit/archive/2009/04/21/80633.html http://www.cnblogs.com/xudong-bupt/p/3433506.html