递归、分治、排序、字典树

题意：

恋爱让人迷醉，却也让人苦恼。
LFgg恋爱了，棉花糖般甜蜜。
LFgg每天花13个小时与NPY聊天，直到期中考试，LFgg考了68分为止。
LFgg终于醒悟过来，他花在聊天上的时间太多了，可是他又不愿意把NPY晾在一边。
所以，LFgg决定学会时间管理，在聊天的间隙学习。
为此，他决定好好***自己的输入法。

“前缀”是指一个从开头开始的字串，例如：“LOVE”的所有前缀是“L”，“LO”，“LOV”，“LOVE”。空字符串不被认为是一个前缀。
LFgg希望他能只用前缀，就能唯一确定一个完整的单词，这样就能大大缩短打字所需的时间。
为此，他决定交给你一个任务，给你LFgg的常用词汇表，希望你能帮他找出每个词的最短的能唯一表示这个词的前缀。
当然，一个完整的单词的优先级大于某个单词的一个前缀。（不然不就没法表示了嘛）

输入
输入包含最少2行最多1000行，每行代表一个单词，单词包含1到20个小写英文字母。

输出
对于每个单词，先输出其原来的单词，然后一个空格，输出其简略形式。

样例输入
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
样例输出
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
提示
样例输入中的“carbohydrate”可以被简略成“carboh”但是不能被简略成“carbo”因为有“carbon”的存在。
但是“car”这个单词可以被表示成“car”而不受别的以“car”开头的单词的影响因为“car”是个完整的单词，拥有最高的表示优先级。

分析

这一提并不难，解题思路还是很容易能找到的，现实中我却花了很多时间，是因为对思路还是不够清晰，递归写的不是很熟练。

我们可以很容易的想，从第一位的字母开始，不断地进行比较，看每一个单词在该位数的字符。
比如对于单词
abcd
adcr
bce
bbff
我们先比较第一位:
对于单词1，第一位为a
对于单词2、第一位为a
对于单词3、第一位为b
对于单词4、第一位为b
我们发现，有a有b那么其实第一位是单词a的单词和第一位是单词b的单词其实已经区分开来了。
我们下一步其实要区分
单词1与单词2
单词3与单词4
从第二位开始区分
这一步我们递归就好了！！！
递归的出口为当要区分的单词只有一个时，直接返回截至此位数的字串，这就是该单词的答案。

如此的话我们很容易就想先对单词排一下序。这样相似度高的单词就相互紧挨在一起了。
那么我们进行操作时会方便许多。

但是、上述的思路是有一个漏洞的！！
如果，我们遇到了在该点无字符的单词怎么办？

即对于这种情况：
单词1： aa
单词2：a
他们在第一位比较时，被分到了一组。现在要进行第二位比较了。我们发现单词2没有第二位？！

如果单词在需要比较的位数上没有字符的话，那么该单词的最终答案就是其本身，
记录下答案、直接将其从比较集中踢出去就好了。

代码如下、注意细节：

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
const int max_n = 1500;
string in[max_n];
string out[max_n];
map<string, int> ans;
int n = 0;

void solve(int site,int l,int r) {
    if (r - l == 1) {
        ans[in[l]] = site;
        return;
    }
    int left = l;
    for (int i = l;i < r;i++) {
        if (in[i].size() <= site) {
            left++;ans[in[i]] = site;
            continue;
        }

        if (i == r - 1 || in[i][site] != in[i + 1][site]) {
            solve(site + 1, left, i + 1);
            left = i+1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    string s;
    while (cin >> s) {
        in[n] = s;
        out[n] = s;
        n++;
    }n++;
    sort(in, in + n);
    solve(0,0,n);
    for (int i = 0;i < n;i++) {
        if (out[i] == "")continue;
        cout << out[i] << " " << out[i].substr(0,ans[out[i]]) << endl;
    }
}

写的繁琐、不够简练。