ring.cpp

第四届百度杯编程大赛final解题报告+标程

/**********************************************************************
Author: Sherlock
Created Time:  2008-10-28 16:24:47
File Name: 
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int   maxint  =   0x7FFFFFFF;
const int   maxSize =   10000 + 10;
const int   maxN    =   50 + 3;
const int   maxM    =   100;

int         n, m, len, num, total;
int         fail[maxSize], que[maxSize], edge[maxSize][26], w[maxM], f[maxN][maxSize], pre[maxN][maxSize], str[maxN], ch[maxN][maxSize];
char        s[maxSize];
bool        hash[maxSize];

struct      list_type
{
    char    s[maxN];
}   list[50];

vector  <int>   g[maxSize];

bool            cmp(int c, int k, int x, int y)
{
    if (c != ch[k + 1][y])
        return (c < ch[k + 1][y]);
    y = pre[k + 1][y];
    for (int i = k; i > 0; i --)
    {
        if (ch[i][x] != ch[i][y])
            return ch[i][x] < ch[i][y];
        y = pre[i][y];
        x = pre[i][x];
    }
    return false;
}

void            add_node()
{
    g[total].clear();
    for (int i = 0; i < 26; i ++)
        edge[total][i] = -1;
    total ++;
}

void            insert_trie(int now, int k)
{
    if (k == len)
    {
        g[now].push_back(num ++);
        return ; 
    }
    if (edge[now][s[k] - 'a'] == -1)
    {
        edge[now][s[k] - 'a'] = total;
        add_node();
    }
    insert_trie(edge[now][s[k] - 'a'], k + 1);
}

void            init()
{
    scanf("%d%d", &n, &m);
    num = total = 0;
    add_node();
    for (int i = 0; i < m; i ++)
    {
        scanf("%s", s);
        len = strlen(s);
        for (int j = 0; j < len / 2; j ++)
            swap(s[j], s[len - 1 - j]);
        insert_trie(0, 0);
    }
    for (int i = 0; i < m; i ++)
        scanf("%d", &w[i]);
}

void            make()
{
    int t = 0;
    for (int i = 0; i < 26; i ++)
        if (edge[0][i] != -1)
        {
            que[t] = edge[0][i];
            fail[que[t]] = 0;
            t ++;
        }
        else
            edge[0][i] = 0;
    
    for (int h = 0; h < t; h ++)
    {
        int now = que[h];
        for (int i = 0; i < 26; i ++)
            if (edge[now][i] != -1)
            {
                int v = edge[now][i];
                int r = fail[now];
                while (edge[r][i] == -1)
                    r = fail[r];
                fail[v] = edge[r][i];
                for (unsigned int j = 0; j < g[fail[v]].size(); j ++)
                    g[v].push_back(g[fail[v]][j]);
                que[t] = v;
                t ++;
            }
    }
}

struct      Q_type
{
    int     x, y;
}   Q[maxN * maxSize];

void            solve()
{
    make();
    memset(f, -1, sizeof(f));
    Q[0].x = 0;
    Q[0].y = 0;
    f[0][0] = 0;
    for (int h = 0, t = 1; h < t; h ++)
    {
        int k = Q[h].x;
        int now = Q[h].y;
        for (int i = 0; i < 26; i ++)
        {
            int next = now;
            while (edge[next][i] == -1)
                next = fail[next];
            next = edge[next][i];
            if (next == 0 && g[now].size() == 0)
                continue;
            if (f[k + 1][next] == -1 && k + 1 < n)
            {
                Q[t].x = k + 1;
                Q[t].y = next;
                t ++;
            }
            int c = 0;
            for (unsigned int x = 0; x < g[next].size(); x ++)
                c += w[g[next][x]];
            if (f[k + 1][next] < f[k][now] + c || f[k + 1][next] == f[k][now] + c && cmp(i, k, now, next))
            {
                f[k + 1][next] = f[k][now] + c;
                pre[k + 1][next] = now;
                ch[k + 1][next] = i;
            }
        }
    }

    int ans = -1, now = 0, l = 0;
    for (int j = 1; j <= n; j ++)
        for (int i = 1; i < total; i ++)
            if (g[i].size() > 0)
                if (f[j][i] > ans || f[j][i] == ans && j == l && cmp(ch[j][i], j - 1, pre[j][i], now))
                {
                    ans = f[j][i];
                    now = i;
                    l = j;
                }
    
    for (int i = l; i > 0; i --)
    {
        str[i] = ch[i][now];
        now = pre[i][now];
    }
    for (int i = l; i > 0; i --)    
        printf("%c", 'a' + str[i]);
    printf("\n");
}

int             main()
{
    int test_num;
    scanf("%d", &test_num);
    while (test_num > 0)
    {
        test_num --;
        init();
        solve();
    } 
    return 0;
}