[AC 自動機]
/OwO/就是要用nullptr
#include<queue>
#include<cstdio>
using namespace std;
#define nullptr (node*) nptr
void* nptr;
class node{
public:
node(){
for(int lx = 0;lx < 27;lx++)
child[lx] = nullptr;
failed = nullptr;
n = 0;
reset();
return;
}
~node(){
for(int lx = 0;lx < 27;lx++)
if(child[lx] != nullptr)
delete child[lx];
return;
}
void reset(){
counted = false;
return;
}
node* child[27];
node* failed;
int n;
bool counted;
};
class actrie{
public:
actrie(){ root = new node;}
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];
}
prc->n++;
return;
}
void make(){
queue<node*> que;
root->failed = nullptr;
root->counted = true;
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;
node* nn = prc->failed;
while(nn != nullptr and nn->child[lx] == nullptr){
nn = nn->failed;
}
if(nn != nullptr)
nn = nn->child[lx];
if(nn == nullptr)
nn = root;
prc->child[lx]->failed = nn;
que.push(prc->child[lx]);
}
}
return;
}
int query(const char* inp)const{
int cnt = 0;
node* ptr = root;
for(int lx = 0;inp[lx];lx++){
int ind = inp[lx]-'a';
while(ptr->child[ind] == nullptr and ptr != root)
ptr = ptr->failed;
ptr = ptr->child[ind];
if(ptr == nullptr) ptr = root;
node* prc = ptr;
while(not prc->counted){
cnt += prc->n;
prc->counted = true;
prc->n = -1; //
prc = prc->failed;
}
}
return cnt;
}
~actrie(){delete root;}
private:
node* root;
};
char dest[1000005];
int main(){
int T;scanf("%d", &T);while(T--){
int n;scanf("%d", &n);
actrie ac;
for(int lx = 0;lx < n;lx++){
char inp[55];scanf("%s", inp);
ac.insert(inp);
}
ac.make();
scanf("%s", dest);
printf("%d\n", ac.query(dest));
}return 0;}
沒有留言:
張貼留言