首页 > 代码库 > hdu模版水题目2896

hdu模版水题目2896

没啥好说的。代码注释,可以秒懂

//照打的。跟模板的差别是引入了used数组和一个flag标记#include <cstdio>#include <cstring>#include <queue>using namespace std;const int maxn = 510*200;int ch[maxn][128],fail[maxn],end[maxn];int root,sz,cnt;char str[10010];bool used[510];int newnode(){    memset(ch[sz],-1,sizeof(ch[sz]));//初始化为-1    end[sz] = 0;    return sz++;}void init(){    sz = 0;    root = newnode();}void insert(char *str,int id){    int len = strlen(str);    int now = root;    for(int i = 0;i < len;i++){        int &tmp = ch[now][str[i]];        if(tmp == -1)   tmp = newnode();        now = tmp;    }    end[now] = id;//记录当前单词的id}void getfail(){    queue<int> q;    fail[root] = root;    for(int i = 0;i < 128;i++){        int &tmp = ch[root][i];        if(tmp == -1)   tmp = root;        else{            fail[tmp] = root;            q.push(tmp);        }    }    while(!q.empty()){        int now = q.front();q.pop();        for(int i = 0;i < 128;i++){            if(ch[now][i] == -1){                ch[now][i] = ch[fail[now]][i];            }else{                fail[ch[now][i]] = ch[fail[now]][i];                q.push(ch[now][i]);            }        }    }}//传入的id是为了输出时的方便void query(char *str,int id){    int len = strlen(str);    int now = root;    int flag = 0;    memset(used,0,sizeof(used));    for(int i = 0;i < len;i++){        now = ch[now][str[i]];        int tmp = now;        //以前的代码是这样的:        /*          while(tmp != root && val[tmp]){            val[tmp];            val[tmp] = 0;           tmp = fail[tmp];          }           *///在这里行不通,因为为了避免重复把标记改动了,对另外一个单词进行查询的时候就出错        while(tmp != root){            //如果是单词末尾id!=0            if(end[tmp]){                //标记改为1                flag = 1;                //此处used标为1                used[end[tmp]] = 1;            }            tmp = fail[tmp];        }    }    //表示在此串中存在单词    if(flag){        cnt++;        printf("web %d:",id);        //遍历一遍,输出used标为1的id        for(int i = 0;i < 510;i++){            if(used[i]) printf(" %d",i);        }        printf("\n");    }}int main(){    init();    int n,m;    scanf("%d",&n);    for(int i = 1;i <= n;i++){        scanf("%s",str);        insert(str,i);    }    getfail();    cnt = 0;    scanf("%d",&m);    for(int i = 1;i <= m;i++){        scanf("%s",str);        query(str,i);    }    printf("total: %d\n",cnt);    return 0;}