UVA 1449 Dominating Patterns

[AC自動機]

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define nullptr ((node*) ntpr)
void* ntpr;
class node{
public:
node(){
for(int lx = 0;lx < 26;lx++)
child[lx] = nullptr;
fail = nullptr;
exist = false;
wordindex = -1;
return;
}
~node(){
for(int lx = 0;lx < 26;lx++)
if(child[lx] != nullptr)
delete child[lx];
return;
}
node* child[26];
node* fail;
bool exist;
int wordindex;
};
class actrie{
public:
actrie(){
root = new node;
_sz = 0;
}
~actrie(){
delete root;
for(int lx = 0;lx < pats.size();lx++)
delete pats[lx];
return;
}
void insert(const char* inp){
node* prc = root;
for(int lx = 0;inp[lx];lx++){
int ch =  inp[lx] - 'a';
if(prc->child[ch] == nullptr)
prc->child[ch] = new node;
prc = prc->child[ch];
}
if(prc->exist == false){
prc->exist = true;
prc->wordindex = _sz;
char* instr = new char[strlen(inp)+2];
strcpy(instr, inp);
//printf("%s -> %d\n", inp, _sz);
pats.push_back(instr);
_sz++;
}else{
printf("%d\n", 1/0);
}
return;
}
void make(){
queue<node*> que;
que.push(root);
while(que.size()){
node* prc = que.front(); que.pop();
for(int lx = 0;lx < 26;lx++){
if(prc->child[lx] == nullptr) continue;
que.push(prc->child[lx]);
node* ff = prc->fail;
while(ff != nullptr and ff->child[lx] == nullptr)
ff = ff->fail;
if(ff != nullptr)
ff = ff->child[lx];
if(ff == nullptr) ff = root;
prc->child[lx]->fail = ff;
}
}
return;
}
int query(vector<char*>& re, const char* inp){
node* ptr = root;
int cnt[160]; for(int lx = 0;lx < 160;lx++)cnt[lx] = 0;
for(int lx = 0;inp[lx];lx++){
int ch = inp[lx]-'a';
while(ptr != root and ptr->child[ch] == nullptr)
ptr = ptr->fail;
ptr = ptr->child[ch];
if(ptr == nullptr) ptr = root;
node* prc = ptr;
while(prc != root){
if(prc->exist){
//printf("word index = %d\n", prc->wordindex);
cnt[prc->wordindex]++;
}
prc = prc->fail;
}
}
//printf("gather ok!\n");
int max_ind = 0;
for(int lx = 1;lx < pats.size();lx++)
if(cnt[lx] > cnt[max_ind])
max_ind = lx;
//if(cnt[max_ind] == 0) return 0;
for(int lx = 0;lx < pats.size();lx++){
if(cnt[max_ind] == cnt[lx])
re.push_back(pats[lx]);
}
return cnt[max_ind];
}
int size()const{return _sz;}
private:
node* root;
vector<char*> pats;
int _sz;
};
char buf[2000000];
int main()
{
int n;
for(;;){
scanf("%d", &n);
if(n == 0) break;
actrie act;
while(n--){
char inp[200];
scanf("%s", inp);
act.insert(inp);
}
act.make();
scanf("%s", buf);
vector<char*> gg;
printf("%d\n", act.query(gg, buf));
for(int lx = 0;lx < gg.size();lx++){
printf("%s\n", gg[lx]);
}
}
return 0;
}