HDU 4117 GRE Words

题目意思   就是给你  N 个单词，然后按照  顺序 后面一个单词是前面一个单词的字串，则可以记忆；每个单词有自己的价值；要求最大价值；

方法        这题  没有 刷掉；要用到  线段数等数据结构来优化；模仿了一个超时的版本；  也就是先建树，然后一个一个字符的插入，上面 那 spoj 上的dp 方法类似；就是，如果这个字符能成为一个单词的字串；则用记录最优值；在最底层的时候把价值全部加上去；明显是超时的， 因为对每个节点来说，都要找他的所有最长前缀，不然就会wa 因为单词可以重复，可能在后面的单词里面会价值会发生改变，变大了，不能保存最优值；

超时了   谁能教我  优化

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

struct date
{
    date *next[26],*fail;
    int sum,cnt;
    bool falg;
}tree[1123456],*que[1123456],*root;

int    res[21234],tail,head,ptr,N;
string str[21234];

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

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

void insert( int i,int val )
{
    date *temp = root;
    for( int j = 0; j < str[i].length(); j++ )
    {
        int num = str[i][j] - 'a';
        if( temp->next[num] == NULL )
            temp->next[num] = creat_node();
        temp = temp->next[num];
    }
}

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];
            que[tail++] = temp->next[i];
        }
        else
        {
            if( temp == root ) temp->next[i] = root;
            else               temp->next[i] = temp->fail->next[i];
        }
    }
}

void query( int i,int val )
{
    date *patten,*temp = root;
    int Max = 0;
    for( int j = 0; j < str[i].length(); j++ )
    {
        int num = str[i][j] -'a';
        temp = temp->next[num];
        Max = max( Max,temp->sum );
        patten = temp;
        while( patten != root )
        {
            Max = max( Max,patten->sum );
            patten = patten->fail;
        }
    }
    temp->sum = Max + val;
    res[i] = Max + val;
}

int main( )
{
    int val[21234],k = 1,T;
    scanf("%d",&T);
    while( T-- )
    {
        scanf("%d",&N);
        inint( );
        memset( res,0,sizeof(res) );
        for( int i = 1; i <= N; i++ )
        {
            cin>>str[i]>>val[i];
            if( val > 0 ) insert( i,val[i] );
        }
        build_AC( );
        for( int i = 1; i <= N ;i++ )
        if( val[i] > 0 )
            query( i,val[i] );
        int ans = 0;
        for( int i = 1; i <= N; i++ )
        ans = max( ans,res[i] );
        printf( "Case #%d: %d\n",k++,ans);
    }
    return 0;
}

/*

7 7
aaaa 12
aa 25
aaa 12
aaaaa 1
aaaaa 5
aaa 13
a 11

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

*/