Submission #1126560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126560		chenwz	Lozinke (COCI17_lozinke)	C++20	100 / 100	315 ms	16548 KiB

lozinke

// [COCI2017-2018#1] Lozinke
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, ans = 0;
  cin >> n;
  vector<string> ps(n);
  map<string, int> cnt;
  for (string& p : ps) {
    cin >> p;
    set<string> ss;  // 记录p的所有不同的子串
    for (int i = 0, len = p.length(); i < len; i++)  // p的所有子串p[i,i+j)
      for (int j = 1; j <= len - i; j++) ss.insert(p.substr(i, j));
    for (const string& s : ss) ++cnt[s];
  }
  for (const string& p : ps) ans += cnt[p] - 1;  // p作为子串出现几次?
  cout << ans << "\n";
  return 0;
}
// AC 100

• Subtask 1: 100 / 100