AC自动机

bzoj1030 [JSOI2007]文本生成器

Description 　　JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：阅读更多…

由elijahqi，2年前

AC自动机

BJ 集训测试13 钢琴

题意给一个序列（<=1e6）给一个字符集大小为n且<=100 每次1/n的概率生成其中阅读更多…

由elijahqi，2年前

AC自动机

luogu3796 【模板】AC自动机（加强版）

题目描述有 N N 个由小写字母组成的模式串以及一个文本串 T T 。每个模式串可能会在文本串中出阅读更多…

由elijahqi，2年前

AC自动机

HDU2222

#include<cstdio>
#include<cstring>
int const N1=55;
int const N2=1100000;
int case1;
char str1[N1],str2[N2];
int idh,n,ans;
struct node{
    int word,id,ch2;
    char ch1;
    node *next[27],*fail;
    node(){
        id=0;
        word=0;
        ch1=' ';
        fail=NULL;
        ch2=0;
        for (int i=1;i<=26;++i) next[i]=NULL;
    }
};
node *root;
void insert1(char s[]){
    int l=strlen(s);
    node *p=root;
    for (int i=0;i<l;++i){
        int x=s[i]-'a'+1;
        if (p->next[x]==NULL) {
            p->next[x]=new node();
            p->next[x]->id=++idh;
            p->next[x]->ch1=s[i];

        }
        p=p->next[x];
    }
    p->word++;
    return;
}
/*void print1(node* p){
    for (int i=1;i<=26;++i) if (p->next[i]!=NULL) {
        printf("%d%d%c\n",p->next[i]->word,p->next[i]->id,p->next->ch1)
        print1(p->next[i]);
    }
}*/
node *d[10000];
void print1(node* p){
    int op=-1,cl=0;
    node *p1,*p2;
    d[cl]=p;
    while (op<cl){
        ++op;
        p1=d[op];
        printf("a:%d %d %c %d\n",p1->word,p1->id,p1->ch1,p1->ch2);
        for (int i=1;i<=26;++i){
            if (p1->next[i]!=NULL){
                p2=p1->next[i];
                printf("b:%d %d %c %d\n",p2->word,p2->id,p2->ch1,p2->ch2);
                d[++cl]=p2;
            }
        }
    }

}
node *data[550000];
void fail1(){
    int op=-1;
    int cl=0;
    data[cl]=root;
    while(op<cl){
        node *p=data[++op];
        for(int i=1;i<=26;++i){
            if(p->next[i]!=NULL){
                ++cl;
                data[cl]=p->next[i];

            node *p1=p->fail;
            while(p1!=NULL&&p1->next[i]==NULL) p1=p1->fail;
            if(p1==NULL){
                p->next[i]->fail=root;
                p->next[i]->ch2=root->id;
            }else{
                p->next[i]->fail=p1->next[i];
                p->next[i]->ch2=p1->next[i]->id;
            }
            }
        }
    }
}
void query(char s[]){
    node *p=root;
    int l=strlen(s);
    //printf("%s",s);
    for(int i=0;i<l;++i){
        int x=s[i]-'a'+1;
        while(p!=NULL&&p->next[x]==NULL) p=p->fail;
        if (p==NULL){
            p=root;continue;
        }
        p=p->next[x];
        node *p1=p;
        while(p1!=NULL){
            if (p1->word!=0){
                ans+=p1->word;p1->word=0;
            }
            p1=p1->fail;
        }
    }
}
/*void fail1(){
    int op=-1,cl=0;
    data[cl]=root;
    while (op<cl){
        node *p=data[++op];
        for (int i=1;i<=26;++i){
            if (p->next[i]!=NULL){

            }
        }

    }
}*/
int main(){
    freopen("hdu2222.in","r",stdin);
    //freopen("hdu2222.out","w",stdout);
    scanf("%d",&case1);
    while(case1--){
        idh=0;
        root = new node();
        //printf("%d",root->id);
        scanf("%d",&n);
        for (int i=1;i<=n;++i){
            scanf("%s",str1);    
            insert1(str1);
        }
        //print1(root);
        fail1();
        //print1(root);
        scanf("%s",str2);
        ans=0;
        query(str2);
        printf("%d\n",ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include<cstdio>

#include<cstring>

int const N1=55;

int const N2=1100000;

int case1;

char str1[N1],str2[N2];

int idh,n,ans;

struct node{

int word,id,ch2;

char ch1;

node *next[27],*fail;

node(){

id=0;

word=0;

ch1=' ';

fail=NULL;

ch2=0;

for (int i=1;i<=26;++i) next[i]=NULL;

}

};

node *root;

void insert1(char s[]){

int l=strlen(s);

node *p=root;

for (int i=0;i<l;++i){

int x=s[i]-'a'+1;

if (p->next[x]==NULL) {

p->next[x]=new node();

p->next[x]->id=++idh;

p->next[x]->ch1=s[i];

}

p=p->next[x];

}

p->word++;

return;

}

/*void print1(node* p){

for (int i=1;i<=26;++i) if (p->next[i]!=NULL) {

printf("%d%d%c\n",p->next[i]->word,p->next[i]->id,p->next->ch1)

print1(p->next[i]);

}

}*/

node *d[10000];

void print1(node* p){

int op=-1,cl=0;

node *p1,*p2;

d[cl]=p;

while (op<cl){

++op;

p1=d[op];

printf("a:%d %d %c %d\n",p1->word,p1->id,p1->ch1,p1->ch2);

for (int i=1;i<=26;++i){

if (p1->next[i]!=NULL){

p2=p1->next[i];

printf("b:%d %d %c %d\n",p2->word,p2->id,p2->ch1,p2->ch2);

d[++cl]=p2;

}

node *data[550000];

void fail1(){

int op=-1;

int cl=0;

data[cl]=root;

while(op<cl){

node *p=data[++op];

for(int i=1;i<=26;++i){

if(p->next[i]!=NULL){

++cl;

data[cl]=p->next[i];

node *p1=p->fail;

while(p1!=NULL&&p1->next[i]==NULL) p1=p1->fail;

if(p1==NULL){

p->next[i]->fail=root;

p->next[i]->ch2=root->id;

}else{

p->next[i]->fail=p1->next[i];

p->next[i]->ch2=p1->next[i]->id;

}

void query(char s[]){

node *p=root;

int l=strlen(s);

//printf("%s",s);

for(int i=0;i<l;++i){

int x=s[i]-'a'+1;

while(p!=NULL&&p->next[x]==NULL) p=p->fail;

if (p==NULL){

p=root;continue;

}

p=p->next[x];

node *p1=p;

while(p1!=NULL){

if (p1->word!=0){

ans+=p1->word;p1->word=0;

}

p1=p1->fail;

}

/*void fail1(){

int op=-1,cl=0;

data[cl]=root;

while (op<cl){

node *p=data[++op];

for (int i=1;i<=26;++i){

if (p->next[i]!=NULL){

}

}*/

int main(){

freopen("hdu2222.in","r",stdin);

//freopen("hdu2222.out","w",stdout);

scanf("%d",&case1);

while(case1--){

idh=0;

root = new node();

//printf("%d",root->id);

scanf("%d",&n);

for (int i=1;i<=n;++i){

scanf("%s",str1);

insert1(str1);

}

//print1(root);

fail1();

//print1(root);

scanf("%s",str2);

ans=0;

query(str2);

printf("%d\n",ans);

}

return 0;

}

由elijahqi，3年前

AC自动机

HDU2896

#include<cstdio>
#include<cstring>
int n,m;bool ans[550];
char str1[220],str2[11000];
struct node{
    int word,id;
    node *next[129],*fail;
    node(){
        id=0;
        for (int i=1;i<=128;++i) next[i]=NULL;
        fail=NULL;
    }
};
node *root;
void insert1(char s[],int x){
    int l=strlen(s);
    node *p=root;
    for (int i=0;i<l;++i){
        int xx=s[i];
        if (p->next[xx]==NULL)  p->next[xx]=new node();
        p=p->next[xx];
    }
    p->id=x;
}
node *d[550];
void fail1(){
    int op=-1,cl=0;
    d[cl]=root;

    while (op<cl){
        node *p=d[(++op)%500];
        //printf("11111\n");
        //printf("%d %d\n",op,cl);
        for (int i=1;i<=128;++i){
            if (p->next[i]!=NULL){

                d[(++cl)%500]=p->next[i];

                node *p1=p->fail;
                while (p1!=NULL&&p1->next[i]==NULL) {
                    p1=p1->fail; //printf("sss");    
                }
                if (p1==NULL){
                    p->next[i]->fail=root;
                }else{
                    p->next[i]->fail=p1->next[i];
                }
            }    
        }


    }
}
void query(char s[]){
    node *p=root;
    int l=strlen(s);
    for (int i=0;i<l;++i){
        int x=s[i];
        while (p!=NULL&&p->next[x]==NULL) p=p->fail;
        if (p==NULL){
            p=root;continue;
        }
        p=p->next[x];
        node *p1=p;
        while (p1!=NULL){
            if (p1->id!=0){
                ans[p1->id]=true;
            }
            p1=p1->fail;
        }
    }

}
int check(){
    for (int i=1;i<=n;++i) {
        if (ans[i]==true) return 1;
    }
    return 0;
}
int main(){
    freopen("hdu2896.in","r",stdin);
    freopen("hdu2896.out","w",stdout);
    scanf("%d",&n);
    root = new node();
    for (int i=1;i<=n;++i) {
        scanf("%s",str1);
        insert1(str1,i);
    }

    fail1();
    //printf("dddd");
    scanf("%d",&m);
    int anss=0;
    for (int i=1;i<=m;++i) {
        scanf("%s",str2);
        memset(ans,false,sizeof(ans));
        query(str2);
        if (check()!=0){
            printf("web %d:",i);
            for (int i=1;i<=n;++i){
                if (ans[i]==true) {
                    printf(" %d",i);
                }


            }
            anss++;
            printf("\n");
        }
        //for (int i=1;i<=n;++i) printf("%d ",ans[i]);

    }
    printf("total: %d\n",anss);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include<cstdio>

#include<cstring>

int n,m;bool ans[550];

char str1[220],str2[11000];

struct node{

int word,id;

node *next[129],*fail;

node(){

id=0;

for (int i=1;i<=128;++i) next[i]=NULL;

fail=NULL;

}

};

node *root;

void insert1(char s[],int x){

int l=strlen(s);

node *p=root;

for (int i=0;i<l;++i){

int xx=s[i];

if (p->next[xx]==NULL) p->next[xx]=new node();

p=p->next[xx];

}

p->id=x;

}

node *d[550];

void fail1(){

int op=-1,cl=0;

d[cl]=root;

while (op<cl){

node *p=d[(++op)%500];

//printf("11111\n");

//printf("%d %d\n",op,cl);

for (int i=1;i<=128;++i){

if (p->next[i]!=NULL){

d[(++cl)%500]=p->next[i];

node *p1=p->fail;

while (p1!=NULL&&p1->next[i]==NULL) {

p1=p1->fail; //printf("sss");

}

if (p1==NULL){

p->next[i]->fail=root;

}else{

p->next[i]->fail=p1->next[i];

}

void query(char s[]){

node *p=root;

int l=strlen(s);

for (int i=0;i<l;++i){

int x=s[i];

while (p!=NULL&&p->next[x]==NULL) p=p->fail;

if (p==NULL){

p=root;continue;

}

p=p->next[x];

node *p1=p;

while (p1!=NULL){

if (p1->id!=0){

ans[p1->id]=true;

}

p1=p1->fail;

}

int check(){

for (int i=1;i<=n;++i) {

if (ans[i]==true) return 1;

}

return 0;

}

int main(){

freopen("hdu2896.in","r",stdin);

freopen("hdu2896.out","w",stdout);

scanf("%d",&n);

root = new node();

for (int i=1;i<=n;++i) {

scanf("%s",str1);

insert1(str1,i);

}

fail1();

//printf("dddd");

scanf("%d",&m);

int anss=0;

for (int i=1;i<=m;++i) {

scanf("%s",str2);

memset(ans,false,sizeof(ans));

query(str2);

if (check()!=0){

printf("web %d:",i);

for (int i=1;i<=n;++i){

if (ans[i]==true) {

printf(" %d",i);

}

anss++;

printf("\n");

}

//for (int i=1;i<=n;++i) printf("%d ",ans[i]);

}

printf("total: %d\n",anss);

return 0;

}

由elijahqi，3年前