url_sherlock.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/**********************************************************************
Author: Sherlock
Created Time:  2009-02-15 18:04:00
File Name: 
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

using namespace std;

const int   maxint  =   0x7FFFFFFF;
const int   maxSize =   100 + 10;
const int   maxLen  =   100 + 10;

int             n;
int             f[maxSize];
char            que[maxSize][maxLen], str[maxLen], buf[10];

map <string, int>           dic;
vector  <pair<int, int> >   list;

bool            cmp(pair<int, int> x, pair<int, int> y)
{
    if (x.second != y.second)
        return x.second > y.second;
    else
    {
        int a = strlen(que[x.first]);
        int b = strlen(que[y.first]);
        for (int i = 0; i < max(a, b); i ++)
            if (que[x.first][i] != que[y.first][i])
                return que[x.first][i] < que[y.first][i];
        return a < b;
    }
}

void            solve()
{
    scanf("%d", &n);
    int cnt = 0;
    memset(f, 0, sizeof(f));
    dic.clear();
    for (int x = 0; x < n; x ++)
    {
        scanf("%s%s", buf, str);
        int len = strlen(str);
        string s;
        if (buf[0] == 'V')
        {
            if (dic.count(str) == 0)
                dic[str] = cnt ++;
            int k = dic[str];
            f[k] ++;
            for (int j = 0; j <= len; j ++)
                que[k][j] = str[j];
        }
        else
        {
            list.clear();
            for (int i = 0; i < cnt; i ++)
            {
                int l = strlen(que[i]);
                if (l < len)
                    continue;
                bool flag = true;
                for (int j = 0; j < len; j ++)
                    if (que[i][j] != str[j])
                    {
                        flag = false;
                        break;
                    }
                if (flag)
                    list.push_back(make_pair(i, f[i]));
            }
            sort(list.begin(), list.end(), cmp);
            for (unsigned int i = 0; i < list.size(); i ++)
                printf("%s\n", que[list[i].first]);
            printf("\n");
        }
    }
}

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