Polycarp’s phone book（unordered_mpa 大法好）

Polycarp's phone book

思路

我用了一种极其暴力的方法，还是STL大法好啊。

在map中存下所有号码的子串，然后再通过一次枚举号码的子串判断其是否再其他的字符中出现，如果没有则输出第一个。

上面的第二次枚举子串应该要按照字串的长度从小到达枚举，这样才能保证输出的第一个一定是我们要找的最优答案。

这样的复杂度\(7e8 * log(7e8)\)应该能过吧，于是我就交了一发，然后tle on test 35了，的确这里的常数实在是有点大了。

然后想一下这里的元素可以是无序的，我们只要保证插入查找的操作就可以了，于是就有了我们的\(unordered\_map\)的做法，顺利的AC了

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 7e4 + 10;
string str[N];
int n;
unordered_map<string, int> mp;
// unormap<string, int> mp;
int main() {
    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> str[i];
        for(int j = 1; j < 10; j++)//先枚举长度，
            for(int k = 0; k < 10 && j + k < 10; k++) {//枚举字符串的起始位置
                string temp = "";
                for(int l = 0; l < j; l++)
                    temp += str[i][l + k];
                if(mp[temp] == 0 || mp[temp] == i)
                    mp[temp] = i;
                else mp[temp] = n + 1;
            }
    }
    // for(unordered_map<string, int> :: iterator it = mp.begin(); it != mp.end(); it++)
    //     cout << it->first << " " << it->second << "\n";
    int flag;
    for(int i = 1; i <= n; i++) {
        flag = 0;
        for(int j = 1; j < 10; j++) {
            for(int k = 0; k < 10 && j + k < 10; k++) {
                string temp = "";
                for(int l = 0; l < j; l++)
                    temp += str[i][l + k];
                if(mp[temp] != n + 1) {
                    flag = 1;
                    cout << temp << "\n";
                }
                if(flag)    break;
            }
            if(flag)    break;
        }
    }
    return 0;
}