算法题：Abbreviated Aliases

问题描述

You are the owner of a large successful internet site with lots of users. All these users have chosen an alias of exactly L characters for logging into the site. Recently, you noticed that you started running into disk space issues: storing all these aliases takes up a lot of data!

You do not have enough money to buy extra storage, so you are looking for ways to reduce the storage space needed. A friend gives you the following compression idea that might help: instead of storing the full alias for each user, you might get away with only storing a prefix of that alias, as long as no other alias has the same prefix. For example, if you just have the aliases james and jacob, you can store only jam and jac and still be able to identify them both.

This idea sounds quite interesting to you, and you are looking forward to finally having more space available on your disk again. You would like to find out how much space you need to store all aliases using this compression technique.

输入格式

The input consists of：

• One line with two integers N,L(2≤N≤104,1≤L≤103),the number of aliases and the length of each alias.
• N lines, each with an alias：a string consisting of exactly L English lowercase characters(a-z), Each alias is unique.

输出格式

Output the total number of characters you still need to store if you apply this compression technique.

样例1

输入

2 5
james
jacob

输出

6

样例2

输入

4 4
xxxx
yxxx
xxyx
yxxy

输出

14

解决方案

思路

深度优先搜索

代码

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<string> ve;

int dfs(const vector<int> &sve, int ans = 0) {
    if (sve.size() == 1) {
        return ans;
    }

    map<char, vector<int>> m;
    for (int i = 0; i < sve.size(); ++i) {
        const string &buf = ve[sve[i]];
        m[buf[ans]].push_back(sve[i]);
    }

    int sum = 0;
    for (const auto &item: m) {
        sum += dfs(item.second, ans + 1);
    }

    return sum;
}


int main() {

    int n;
    int l;
    cin >> n >> l;


    vector<int> sve;
    for (int i = 0; i < n; ++i) {
        char buf[10005];
        cin >> buf;
        ve.push_back(buf);
        sve.push_back(i);
    }
    cout << dfs(sve);

    return 0;
}