COCI2017-2018-1-Lozinke

题意

$n$ 个字符串，统计每个字符串作为其他字符串的子串出现的次数。 $n \le 20000$。同时每个字符串的长度不超过 $10$。

分析

每个字符串的长度不超过 $100$，所以每个字符串的子串最多有 $C_{11}^2$ 个。因此，我们建立数组 $cnt$。$cnt[s]$ 表示 $s$ 在给出的 $n$ 个字符串中，作为子串的数量。

现在，我们枚举每个字符串的每一个子串 $s$，令 $cnt[s]$ 增加 $1$，表示 $s$ 是当前字符串的子串。如果当前字符串存在多个相同的子串。则只计算一次。

如果采用 unordered_set 来统计结果，对每个保存的元素可以做到 $O(1)$ 的时间复杂度，因此，整个问题的时间复杂度为 $O(100n)$。

int n;
cin >> n;
vector<string> pw(n);
unordered_map<string, int> cnt;
for (int i = 0; i < n; i++) {
    cin >> pw[i];
    unordered_set<string> s;
    for (int l = 0; l < pw[i].length(); l++)
        for (int len = 1; len + l <= pw[i].length(); len++)
            s.insert(pw[i].substr(l, len));

    for (auto &t : s) cnt[t]++;
}

int ans = 0;
for (auto &t : pw) ans += cnt[t];

cout << ans - n << endl;