AC自动机妙用

理解题意之后,很自然的想到了用AC自动机搞,结果网上一搜,全是暴搜,按照自己的思想,AC自动机搞起,果然在提交了数次之后,看到了Accept。

AC自动机需要三个步骤:

第一步:建立字典树;

第二步:为字典树建立 Fail 指针 ;

第三步:进行匹配;

#include<iostream>
#include<string>
#include<string.h>
#include<cctype>
#include<queue>
#include<stdio.h> #define max(x,y) ((x) > (y) ? (x) : (y)) using namespace std ; struct Node {
Node *next[26] ;
Node *fail ;
bool is_over ;
int len ;
}; Node* new_node() {
Node *root = new Node ;
root ->fail = NULL ;
for(int i = 0 ; i< 26 ; i++)
root->next[i] = NULL ;
root ->is_over = false ;
return root ;
} void build_tree( Node *root , char *s ) {
int len = strlen(s) ;
for(int i = 0 ; i < len ; i++) {
if(root->next[s[i] - 'a'] == NULL)
root->next[s[i] - 'a'] = new_node() ;
root = root ->next[s[i] - 'a'] ;
}
root ->is_over = true ;
root ->len = len ;
} void build_fail(Node *root) {
Node *r = root ;
queue< Node* > q ;
q.push(root) ;
while(!q.empty()) {
r = q.front() ;
q.pop() ;
Node *p = r ;
for(int i = 0 ; i < 26 ; i++) {
if(p->next[i] != NULL) {
if(p == root) {
p->next[i]->fail = root ;
q.push(p->next[i]) ;
continue ;
}
while(r->fail->next[i] == NULL && r ->fail != root)
r = r->fail ;
if(r->fail ->next[i] != NULL)
p ->next[i]->fail = r ->fail ->next[i] ;
else
p ->next[i] ->fail = root ;
q.push(p->next[i]) ;
}
}
}
} int A_C(Node *root , char *s) {
int len = strlen(s) ;
Node *r = root ;
int count = 0 ;
for(int i = 0 ; i < len ; i++) {
if(!isalpha(s[i]))
continue ;
if(r->next[s[i]-'a'] != NULL) {
r = r ->next[s[i]-'a'] ;
if(r->is_over && !(islower(s[i+1])) && !(islower(s[i - r->len])) )
count++ ;
}
else {
while(r->next[s[i]-'a'] == NULL && r != root )
r = r ->fail ;
if(r ->next[s[i] - 'a'] != NULL)
r = r ->next[s[i] - 'a'] ;
else
r = root ;
if(r->is_over && (!(isalpha(s[i+1])) ) && !(islower(s[i - r->len])) )
count++ ;
}
} return count ;
} int main() {
int n , m ;
int t = 1 ;
while(scanf("%d%d",&n,&m) == 2) {
Node *root = new_node() ;
Node *r = root ;
while(n--) {
char s[30] ;
scanf("%s",&s) ;
getchar() ;
build_tree(root,s) ;
root = r ;
}
r->fail = NULL ;
root = r ;
build_fail(r) ;
char str[30][100] ;
char str1[30][100] ;
int count[30] = {0} ;
int ma = 0 ;
for(int i = 0 ; i < m ; i++) {
gets(str[i]) ;
strcpy(str1[i],str[i]) ;
int len = strlen(str[i]) ;
for(int j = 0 ; j < len ; j++)
if(isupper(str[i][j]))
str[i][j] += 32 ;
count[i] = A_C(root,str[i]) ;
ma = max(ma,count[i]) ;
}
cout << "Excuse Set #" << t++ << endl;
for(int k = 0 ; k < m ; k++)
if(count[k] == ma)
cout << str1[k] << endl ;
cout << endl ;
}
return 0 ;
}
上一篇:Oracle使用expdp/impdp迁移数据


下一篇:oracle 11g expdp impdp详细使用方法