Luogu P4421 [COCI2017-2018#1] Lozinke

题目链接：​​传送门​​

一开始直接AC自动机每个串暴力跳fail
显然会T，44分

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int son[26], w, fail;
}t[A];
node tmp[A];
int n, ans, tot; char s[A][15];
void insert(char *s, int rt = 0) {
  for (int i = 0; s[i]; i++) {
    int x = s[i] - 'a';
    if (!t[rt].son[x]) t[rt].son[x] = ++tot;
    rt = t[rt].son[x];
  }
  t[rt].w++;
}
void getfail() {
  queue<int> q;
  for (int i = 0; i < 26; i++) if (t[0].son[i]) q.push(t[0].son[i]);
  while (!q.empty()) {
    int fr = q.front(); q.pop();
    for (int i = 0; i < 26; i++) {
      if (t[fr].son[i]) {
        t[t[fr].son[i]].fail = t[t[fr].fail].son[i];
        q.push(t[fr].son[i]);
      }
      else t[fr].son[i] = t[t[fr].fail].son[i];
    }
  }
}
int acm(char *s) {
  int rt = 0, ans = 0;
  memcpy(tmp, t, sizeof(t));
  for (int i = 0; s[i]; i++) {
    int x = s[i] - 'a';
    rt = t[rt].son[x];
    for (int p = rt; p and ~tmp[p].w; p = t[p].fail) ans += tmp[p].w, tmp[p].w = -1;
  }
  return ans;
}

int main(int argc, char const *argv[]) {
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%s", s[i]) , insert(s[i]);
  getfail();
  for (int i = 1; i <= n; i++) ans += acm(s[i]) - 1;
  cout << ans << endl;
}

然后STL开O2搞过去
把每个子串放到set里
map累计出现次数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
string s[A]; int n, ans;
map<string, int> m;
set<string> v;

int main(int argc, char const *argv[]) {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s[i]; int len = s[i].length();
    v.clear();
    for (int j = 0; j < len; j++) {
      string tmp = "";
      for (int k = j; k < len; k++) {
        tmp += s[i][k];
        v.insert(tmp);
      }
    }
    for (auto it = v.begin(); it != v.end(); it++) m[*it]++;
  }
  for (int i = 1; i <= n; i++) ans += m[s[i]] - 1;
  cout << ans << endl;
}