正文
AC自动机 - 多模式串的匹配 --- HDU 3695 Computer Virus on Planet Pandora
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Problem's Link
Mean:
有n个模式串和一篇文章，统计有多少模式串在文章中出现（正反统计两次）.
analyse:
好久没写AC自动机了，回顾一下AC自动机的知识。
本题在构造文章的时候需要仔细一点，其他没什么Trick，和普通AC自动机做法一样：
build Trie ---> build Fail_Ptr ---> matching_and_count
Time complexity: O(N*L+M)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-19-10.29
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;const int M = ;
class node {
public:
bool flag;
node *fail, *next[];
node() {
flag = false;
fail = NULL;
memset( next, NULL, sizeof next );
}
};
node *root;
queue<node*> q;
char s[M], str[M];void Insert( char *str ) { // build Trie-Tree
node *p = root;
int i = , index;
while( str[i] ) {
index = str[i] - 'A';
if( p->next[index] == NULL )
p->next[index] = new node();
p = p->next[index];
++i;
}
p->flag = true;
}void build_ac_automation( node *root ) { // build fail ptr
root->fail = NULL;
while( !q.empty() ) q.pop();
q.push( root );
while( !q.empty() ) {
node *temp = q.front();
q.pop();
node *p = NULL;
for( int i = ; i < ; ++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( node *root ) { // mathing and count
node *p = root;
int i = , ans = , index;
while( str[i] ) {
index = str[i] - 'A';
while( p->next[index] == NULL && p != root )
p = p->fail;
p = p->next[index];
if( p == NULL )
p = root;
node *temp = p;
while( temp != root && temp->flag ) {
ans++;
temp->flag = false;
temp = temp->fail;
}
i++;
}
return ans;
}inline void build_str( char *s ) {
int len = strlen( s ), cnt = -;
for( int i = ; i < len; ++i ) {
if( s[i] >= 'A' && s[i] <= 'Z' ) {
str[++cnt] = s[i];
continue;
}
if( s[i] == '[' ) {
++i;
int num = ;
for( ; s[i] >= '' && s[i] <= ''; ++i ) {
num = num * + ( s[i] - '' );
}
char ch = s[i];
++i;
for( int j = ; j <= num; ++j )
str[++cnt] = ch;
}
}
str[++cnt] = '\0';
}int main() {
ios_base::sync_with_stdio( false );
cin.tie( );
int Cas;
scanf( "%d", &Cas );
while( Cas-- ) {
root = new node();
int n;
scanf( "%d", &n );
while( n-- ) {
scanf( "%s", s );
Insert( s );
}
build_ac_automation( root );
scanf( "%s", s );
build_str( s );
int ans = query( root );
strrev( str );
ans += query( root );
printf( "%d\n", ans );
}
return ;
}
