HDU 2222 키워드 검색 (AC 자동 템 플 릿)

21149 단어
AC 자동 동 기 는 다 중 모드 가 일치 하 는 알고리즘 이다.대략적인 과정 은 다음 과 같다.
  • 먼저 모든 패턴 문자열 은 Trie 트 리 를 구성 합 니 다. Trie 트 리 의 모든 비 근 노드 는 뿌리 에서 이 점 까지 의 경 로 를 나타 내 는 문자열 입 니 다.
  • 그 다음 에 모든 노드 는 fail 지침 의 값 을 계산 합 니 다. 이 fail 지침 은 이 노드 가 표시 하 는 문자열 의 가장 긴 존재 하 는 접미사 에 대응 하 는 결점 을 가리 키 고 존재 하지 않 으 면 뿌리 를 가리 킵 니 다. 모든 노드 의 fail 을 계산 하 는 데 BFS 를 사용 합 니 다. 예 를 들 어 현재 노드 u 가 팀 을 나 와 아이의 결점 을 확대 하고 계산 하 는 fail, v 는 첫 번 째 k 아이 이 고 fail [v] 의 값 은 특정한 fail 입 니 다.[fail [fail... [u]] k 번 째 아이 결점 이 존재 합 니 다. fail [v] 가 존재 하지 않 으 면 root 입 니 다.
  • 마지막 에 메 인 꼬치 는 Trie 트 리 로 달 려 갑 니 다. 어떤 Trie 트 리 의 노드 가 어 울 리 지 않 으 면 이 노드 fail 포인터 가 가리 키 는 노드 로 달 려 갑 니 다. 그러나 특정한 패턴 꼬치 와 일치 하면 특정한 패턴 꼬치 의 접미사 가 무시 되 었 을 수 있 습 니 다. 그래서 temp 지침 을 사용 하여 누락 된 접미사 가 일치 하지 않 는 지 확인 해 야 합 니 다.
  •  
    이 문 제 는 대략 몇 개의 패턴 문자열, 한 개의 메 인 문자열 을 주 고 몇 개의 패턴 문자열 이 메 인 문자열 에 일치 하 는 지 물 어 보 는 것 이다.
    AC 자동 동기 템 플 릿 문제 입 니 다. 최적화 할 수 있 는 부분 은 특정한 패턴 문자열 이 일치 하 는 것 입 니 다. 다음 에 여 기 를 지나 면 temp 지침 의 과정 을 뛰 어 넘 을 수 있 습 니 다.
     
    코드 는 kuangbin 의 거대 한 블 로 그 를 참고 합 니 다. 너무 간결 합 니 다 (300 + ms):
     1 #include
     2 #include
     3 #include 
     4 using namespace std;
     5 int tn,ch[510000][26],cnt[510000],fail[510000];
     6 void insert(char *s){
     7     int x=0;
     8     for(int i=0; s[i]; ++i){
     9         int y=s[i]-'a';
    10         if(ch[x][y]==0) ch[x][y]=++tn;
    11         x=ch[x][y];
    12     }
    13     ++cnt[x];
    14 }
    15 void init(){
    16     memset(fail,0,sizeof(fail));
    17     queue<int> que;
    18     for(int i=0; i<26; ++i){
    19         if(ch[0][i]) que.push(ch[0][i]);
    20     }
    21     while(!que.empty()){
    22         int x=que.front(); que.pop();
    23         for(int i=0;i<26;++i){
    24             if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
    25             else ch[x][i]=ch[fail[x]][i];
    26         }
    27     }
    28 }
    29 int query(char *s){
    30     int x=0,res=0;
    31     for(int i=0; s[i]; ++i){
    32         int tmp=x=ch[x][s[i]-'a'];
    33         while(tmp){
    34             if(cnt[tmp]>=0){
    35                 res+=cnt[tmp];
    36                 cnt[tmp]=-1;
    37             }else break;
    38             tmp=fail[tmp];
    39         }
    40     }
    41     return res;
    42 }
    43 char S[1100000],T[55];
    44 int main(){
    45     int t,n;
    46     scanf("%d",&t);
    47     while(t--){
    48         tn=0;
    49         memset(ch,0,sizeof(ch));
    50         memset(cnt,0,sizeof(cnt));
    51         scanf("%d",&n);
    52         while(n--){
    53             scanf("%s",T);
    54             insert(T);
    55         }
    56         init();
    57         scanf("%s",S);
    58         printf("%d
    ",query(S)); 59 } 60 return 0; 61 }

     
     
    또한 이전에 배 운 지침 버 전의 지침 버 전 은 더 빨리 달린다 (200 + ms).
     1 #include
     2 #include
     3 #include
     4 using namespace std;
     5 typedef struct Node *pNode;
     6 struct Node{
     7     int cnt;
     8     pNode fail,nxt[26];
     9     Node(){
    10         cnt=0; fail=NULL;
    11         for(int i=0;i<26;++i) nxt[i]=NULL;
    12     }
    13 };
    14 pNode root;
    15 char S[1000100];
    16 void insert(char *s){
    17     pNode p=root;
    18     for(int i=0;s[i];++i){
    19         int index=s[i]-'a';
    20         if(p->nxt[index]==NULL){
    21             p->nxt[index]=new Node;
    22         }
    23         p=p->nxt[index];
    24     }
    25     ++p->cnt;
    26 }
    27 void init(){
    28     queue que;
    29     que.push(root);
    30     while(que.size()){
    31         pNode y=que.front(); que.pop();
    32         for(int i=0;i<26;++i){
    33             if(y->nxt[i]==NULL) continue;
    34             if(y==root){
    35                 y->nxt[i]->fail=root;
    36                 que.push(y->nxt[i]);
    37                 continue;
    38             }
    39             pNode x=y->fail;
    40             while(x&&x->nxt[i]==NULL) x=x->fail;
    41             if(x==NULL) y->nxt[i]->fail=root;
    42             else y->nxt[i]->fail=x->nxt[i];
    43             que.push(y->nxt[i]);
    44         }
    45     }
    46 }
    47 int query(){
    48     int res=0;
    49     pNode x=root;
    50     for(int i=0;S[i];++i){
    51         int index=S[i]-'a';
    52         while(x->nxt[index]==NULL&&x!=root) x=x->fail;
    53         x=x->nxt[index];
    54         if(x==NULL) x=root;
    55         pNode y=x;
    56         while(y!=root){
    57             if(y->cnt>=0){
    58                 res+=y->cnt;
    59                 y->cnt=-1;
    60             }else break;
    61             y=y->fail;
    62         }
    63     }
    64     return res;
    65 }
    66 int main(){
    67     int t,n;
    68     char s[55];
    69     scanf("%d",&t);
    70     while(t--){
    71         root=new Node;
    72         scanf("%d",&n);
    73         for(int i=0;ii){
    74             scanf("%s",s);
    75             insert(s);
    76         }
    77         scanf("%s",S);
    78         init();
    79         printf("%d
    ",query()); 80 } 81 return 0; 82 }

     
    다음으로 전송:https://www.cnblogs.com/WABoss/p/5164457.html

    좋은 웹페이지 즐겨찾기