/ ALGORITHM

2016 Nordic Collegiate Programming Contest B

Problem Information

source: It’s from the kattis

Description

输入法的自动补全是根据用户以前的输入建立了一个字典库,出现频率从上往下递减,每次当用户键入一个或一个以上的字符同时按下 Tab 键后,自动补全会在字典库中从上往下找到包含这几个字符的第一个字符串,然后直接补全。举个栗子,使用输入法的自动补全来键入 “autocorrelation” ,首先输入 “aut” 三个字符,再按下 Tab 键,它匹配到 “autocorrect” ,然后按下两次退格得到 “autocorre” ,最后再输入 “lation” ,这样总共按键 12 次,而直接输入这个单词需要 15 次。

现在按照出现频率给出字典库中的 $n$ 个单词,再给出 $m$ 个待输入单词,求输入每个单词的最小按键次数。

Input

5 5                                                                                   
austria
autocorrect
program
programming
computer
autocorrelation
programming
competition
zyx
austria

Output

12                                                                                    
4
11
3
2

Solution

很容易能发现这是一道最短路的问题,即询问的是从每个单词的首字母到尾字母的最短距离。
我们考虑对于字典库的单词建立字典树,在建树的时候同时建图:

  • 每个单词的每个字母往它之后的那个字母连边。
  • 每个字母往该单词的尾字母连边:若该字母未连接过其它的尾字母,则向当前单词的尾字母连边,这样能确保每次先走频率最高的单词。

AC code

struct Trie                                                                           
{
    const static int CH_NUM = 26;
    int ch[MaxN][CH_NUM];
    int pre[MaxN];
    bool cnt[MaxN];
    int siz;
    void init(){
        CLR(ch);CLR(pre);CLR(cnt);
        siz = 0;
    }
    int ord(char c){
        return c-'a';
    }
    void insert(char* s)
    {
        int u = 0,len = strlen(s);
        for(int i=0;i<len;i++){
            int c = ord(s[i]);
            if(!ch[u][c]) 
            {
                ch[u][c] = ++siz;
                pre[siz] = u;
                if(i!=len-1) cnt[siz] = 1;
                add(u, siz);add(siz, u);
                if(i==len-1 && u && cnt[u]){
                    cnt[u] = 0;
                    int now = pre[u];
                    while(now && cnt[now]){
                        cnt[now] = 0;
                        add(now,siz);
                        now = pre[now];
                    }
                }
            }
            u = ch[u][c];
        }
    }
    int query(char* s)
    {
        int u = 0,len = strlen(s),i;
        for(i=0;i<len;i++){
            int c = ord(s[i]);
            if(ch[u][c])
                u = ch[u][c];
            else break;
        }
        int ans = dis[u] + len-i;
        return ans;
    }
}T;
char str[MaxN];
int main()
{
    int n,m;
    while(~scanf("%d%d", &n, &m))
    {
        T.init();
        init();
        while(n--)
        {
            scanf("%s", &str);
            T.insert(str);
        }
        Dijkstra(T.siz);
        while(m--)
        {
            scanf("%s", &str);
            int ans = T.query(str);
            printf("%d\n", ans);
        }
    }
}