poj 4052 简单题

题意     就是给你N 个单词   和 一篇文章；然后问你  在这篇文章里面有多少个 出现的单词；如果一个单词是一个单词的字串，则只能算一个；

方法    首先用最简单的方法  把字符串解码，然后用模板跑一遍，找到所有单词，然后再用着写被标记的单词  插入字典树，把一路上的字符全部标记；

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

char cha[2550][1123],str[5123456],sss[5123456];
bool vis[2550];

structdate
{
    date *next[26],*fail;
    int tab;
    bool flag;
}tree[3123456],*que[3123456],*root;

int tail,head,ptr,N;

date *creat_node(  )
{
    for( int i = 0; i < 26; i++ )
    tree[ptr].next[i] = NULL;
    tree[ptr].fail = NULL;
    tree[ptr].tab = 0;
    tree[ptr].flag = false;
    return &tree[ptr++];
}

void inint( )
{
    tail = head = ptr = 0;
    root = creat_node( );
    root->fail = root;
}

void insert( char *word,int i )
{
    date *temp = root;
    while( *word )
    {
        int num = *word - 'A';
        if( temp->next[num] == NULL )
            temp->next[num] = creat_node(  );
        temp = temp->next[num];
        word++;
    }
    temp->tab = i;
}

void build_AC( )
{
    que[tail++] = root;
    while( tail > head )
    {
        date *temp = que[head++];
        for( int i = 0; i < 26; i++ )
        if( temp->next[i] != NULL )
        {
            if( temp == root ) temp->next[i]->fail = root;
            else               temp->next[i]->fail = temp->fail->next[i];
            temp->next[i]->flag = true;
            que[tail++] = temp->next[i];
        }
        else
        {
            if( temp == root ) temp->next[i] = root;
            else               temp->next[i] = temp->fail->next[i];
        }
    }
}

int query( char *word )
{
    date *patten,*temp = root;
    while( *word )
    {
        int num = *word - 'A';
        temp = temp->next[num];
        patten = temp->fail;
        vis[temp->tab] = true;
        while( patten != root )
        {
            if( patten->flag )
            {
                    patten->flag = false;
                vis[patten->tab] = false;
            }
            else break;
            patten = patten->fail;
        }
        word++;
    }
    for( int i = 1; i <= N; i++ )
    {
        if( vis[i] )
        {
            date *temp = root;
            int k = 0;
            int len = strlen(cha[i]) - 1;
            while( len-- )
            {
                int num = cha[i][k++] - 'A';
                temp = temp->next[num];
                int t   = temp->tab;
                if( vis[t] )vis[t] = false;
            }
        }
    }
    int ans = 0;
    for( int i = 1; i <= N; i++ )
    if( vis[i] )ans++;
    return ans;
}

int deal( char *word,int t,int x)
{
    bool fell = false;
    int len = strlen(word),num = 0,k = 0;
    for( int i = 0; i < len; i++ )
    {
        if( fell )
        {
            if( word[i] - '0' >= 0 && word[i] - '0' <= 9 )
                num = num*10 +  ( word[i] - '0' );
            else
            {
                while( num-- )sss[k++] = word[i];
                fell = false;
            }
                continue;
        }
        if( word[i] == '[' )
        {
            fell = true; num = 0; continue;
        }
        if( (word[i] - 'A') >= 0 && (word[i] - 'A') <= 25 )
            sss[k++] = word[i];
    }
    sss[k] = '\0';
    if( x )
    {
        for( int i = 0; i < k; i++ )
        cha[t][i] = sss[i];
        cha[t][k] = '\0';
    }
    else
    {
        for( int i = 0; i < k; i++ )
        str[i] = sss[i];
        str[k] = '\0';
    }
    return 0;
}
int main( )
{
    int T,i,j;
    scanf("%d",&T);
    while( T-- )
    {
         scanf("%d",&N); inint( );
         for( i = 1; i <= N; i++ )
         {
             scanf( "%s",&cha[i] );
             deal(cha[i],i,1);
             insert( cha[i],i );
         }
         build_AC( );
         scanf("%s",&str);
         deal(str,0,0);
         memset( vis,false,sizeof(vis) );
         printf("%d\n",query( sss ));
    }
    return 0;
}