UVAOJ 1676

[AC自動機]

為啥不早點AC QAQQQQQQ

是說覺得這種Online方式有點特別@@


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<functional>
#include<cstring>
using namespace std;
#define LL long long int
#define nullptr ((node*) nptr)
void* nptr;
struct StrCompare : public std::binary_function<const char*, const char*, bool> {
public:
    bool operator() (const char* str1, const char* str2) const
    { return std::strcmp(str1, str2) < 0; }
};
typedef map<const char* , int , StrCompare> DICT;
DICT dict;
int dict_query(const char* inp){
if(dict.count(inp) > 0)
return dict[inp];
//printf("add %s\n", inp);
char* nn = new char[strlen(inp)+2];
strcpy(nn, inp);
int sz = dict.size();
dict[nn] = sz;
return sz;
}
bool dict_check(const char* inp){
return(dict.count(inp) > 0);
}
void dict_clear(){
for(DICT::iterator it = dict.begin();it != dict.end();it++)
delete[] it->first;
dict.clear();
return;
}
class node{
public:
node(){
child[0] = nullptr, child[1] = nullptr;
//fail[0] = nullptr, fail[1] = nullptr;
fail = nullptr;
exist = false;
wordindex = -1;
countpoint = 0;
return;
}
~node(){
for(int lx = 0;lx < 2;lx++){
if(child[lx] != nullptr) delete child[lx];
//if(fail[lx] != nullptr) delete fail[lx];
}
return;
}
node* child[2];
node* fail;
bool exist;
int countpoint;
int wordindex;
};

class actrie{
public:
actrie(){
root = new node;
maked = false;
return;
}
void insert(const char *inp){
node* prc = root;
for(int lx =0;inp[lx];lx++){
char ch = inp[lx] - '0';
if(prc->child[ch] == nullptr)
prc->child[ch] = new node;
prc = prc->child[ch];
}
prc->exist = true;
prc->wordindex = dict_query(inp);
return;
}
~actrie(){
delete root;
}
void clear(){
delete root;
root = new node;
maked = false;
return;
}
void make(){
if(maked) return;
queue<node*> que;
root->fail = nullptr;
que.push(root);
while(que.size()){
node* prc = que.front(); que.pop();
for(int lx = 0;lx < 2;lx++){
if(prc->child[lx] == nullptr) continue;
node* nn = prc->fail;
while(nn != nullptr and nn->child[lx] == nullptr)
nn = nn->fail;
if(nn != nullptr)
nn = nn->child[lx];
if(nn == nullptr)
nn = root;
prc->child[lx]->fail = nn;
prc->child[lx]->countpoint = nn->countpoint + prc->child[lx]->exist;
que.push(prc->child[lx]);
}
}
maked = true;
return;
}
LL query(const char* inp){
//if(maked == false) printf("%d\n", 1/0);
//printf("q %s\n", inp);
LL cnt = 0;
node* prc = root;
set<int> counted;
for(int lx = 0;inp[lx];lx++){
int ch = inp[lx]=='1';
while(prc != root and prc->child[ch] == nullptr)
prc = prc->fail;
prc = prc->child[ch];
if(prc == nullptr) prc = root;
cnt += prc->countpoint;
/*node* ptr = prc;
while(ptr != root and counted.count(ptr->wordindex)==0){
cnt += ptr->exist;
if(ptr->wordindex != -1)
counted.insert(ptr->wordindex);
ptr = ptr->fail;
}*/
}
return cnt;
}
void print(){
printf("{");
_printnode(root);
printf("}\n");
return;
}
private:
node* root;
bool maked;
void _printnode(node* rt){
printf("(%d = %d,%d)[ ", rt->wordindex, rt->exist, rt->countpoint);
for(int lx = 0;lx < 2;lx++)
if(rt->child[lx] != nullptr)
printf("%d:", lx), _printnode(rt->child[lx]);
printf("]");
return;
}
};
class ACBST{
public:
ACBST(){
memset(comp, false, sizeof(comp));
comp[base+1] = true;
_size = 0;
}
void setbase(int n){
base = (1<<(int)(ceil(log2(n+3))))-1;
return;
}
~ACBST(){clear();};
void clear(){
for(int lx = 0;lx < line.size();lx++)
delete line[lx];
for(int lx = 1;lx <= line.size()+1+base;lx++)
comp[lx] = 0;
for(int lx = 1;lx <= line.size()+1+base;lx++)
act[lx].clear();
comp[base+1] = true;
line.clear();
return;
}
void add(const char *inp){
if(dict_check(inp) == true) return;
char* ch = new char[strlen(inp)+2];
dict_query(inp);
strcpy(ch,inp);
line.push_back(ch);
comp[line.size()+1+base] = true;
for(int prc = line.size() + 1 + base;prc;prc>>=1)
act[prc].insert(inp);
act[line.size() + 1 + base].make();
//printf("make %d\n", line.size()+1+base);
for(int prc = (line.size()+1+base)>>1;prc;prc>>=1)
if(comp[prc*2] and comp[prc*2+1] and not comp[prc]){
act[prc].make();
comp[prc] = true;
//printf("make %d\n", prc);
}
//printf("inp = %s = ch = %s\n", inp, ch);

return;
}
/*void make(){
base = (1<<(int)(ceil(log2(line.size()+2))))-1;
for(int lx = 0;lx < line.size();lx++)
for(int prc = base+1 + lx+1;prc;prc>>=1)
act[prc].insert(line[lx]);
for(int lx = 1;lx <= base+line.size()+1;lx++)
act[lx].make();
for(int lx = 1;lx <= base+line.size()+1;lx++)
act[lx].print();
return;
}*/
LL query(const char* inp){
if(size() == 0) return 0;
int a = 2;
int b = size()+1;
LL cnt = 0;
int nds[40], ndcnt = 0;
for(a += base-1, b += base+1; a^b^1;a>>=1, b>>=1){
if(~a&1){
//printf("q node at a%d\n", a^1);
nds[ndcnt++] = a^1;
cnt += act[a^1].query(inp);
}
if(b&1){
//printf("%d\n", 1/0);
//printf("q node at b%d\n", b^1);
nds[ndcnt++] = b^1;
cnt += act[b^1].query(inp);
}
}
return cnt;
}
int size(){return line.size();};
private:
int _size;
vector<char*> line;
actrie act[400005];
bool comp[400005];
int base;
};
char gstr[5000005];
ACBST acbst;
struct command{
char* str;
int qsz;
}cmds[100005]; int cmd_cnt;
void swapstr(char *inp, int a, int b){
for(int lx = 0;a+lx < b-lx;lx++){
char tmp = inp[a+lx];
inp[a+lx] = inp[b-lx];
inp[b-lx] = tmp;
}
return;
}
int main()
{int T;scanf("%d", &T);
for(int lt = 1;lt <= T;lt++){
dict_clear();
acbst.clear();
cmd_cnt = 0;
int n;scanf("%d", &n);
acbst.setbase(n);
LL last = 0;
printf("Case #%d:\n", lt);
while(n--){
scanf("%s", gstr);
int len = strlen(gstr+1);
int _last = (int)(last%(LL)len);
swapstr(gstr+1, 0, len-1);
swapstr(gstr+1, 0, len-_last-1);
swapstr(gstr+1, len-_last, len-1);
//printf("operate str = %s\n", gstr+1);
if(gstr[0] == '+'){
acbst.add(gstr+1);
}else{
LL ans = acbst.query(gstr+1);
printf("%I64d\n", ans/(ans>=0));
last = ans;
}
}
}return 0;}