A、Browser Games

题目大意

给出个字符串，你需要输出行。

对于第个字符串来说，你需要在这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。

其次就是你曾经选择过的前缀不能做为前缀出现在这些字符串里面。

卡了空间只允许。

Solution

考点：字符串hash

如果是正序的话比较容易考虑到字典树，但是字典树的空间这题卡空间过不去。

我们倒序的思考，对于最后一个字符串，只需要考虑前字符串里面第一个字符出现了几种就是答案了。

那么接下来如何处理加入的第个字符串。

我们把第个字符串的全部前缀都出来，接下来去一个里面把相同的前缀出现过的下标全部找出来，并且让这些下标在的位置前缀长度即可。然后处理完之后把第个字符串的前缀全部删掉，因为你已经有了它前缀的新字符串了。

这样一路往前递推就可以在的时间内完成这一系列操作。

const int N = 1e5 + 7, bas = 131;

ull p[N];
unordered_map<ull, vector<int>> mp;
int pos[N], ans[N];
string s[N];

int solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        pos[i] = 0;
        p[i] = s[i][0];
        mp[p[i]].push_back(i);
    }

    for (int i = n; i >= 1; --i) {
        ans[i] = mp.size();
        ull pre = 0;
        for (auto& c : s[i]) {
            pre = pre * bas + c;
            auto it = mp.find(pre);
            if (it == mp.end()) continue;

            for (auto& id : it->second) {
                if (id == i)    continue;
                ++pos[id];
                p[id] = p[id] * bas + s[id][pos[id]];
                mp[p[id]].push_back(id);
            }
            mp.erase(it);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }

    return 1;
}