C++(g++ 7.5.0) 解法, 执行用时: 624ms, 内存消耗: 201924K, 提交时间: 2023-06-30 19:41:31

#include <iostream>
#include <vector>

using namespace std;

const int N = 2000010;
const int mod = 1e9 + 7;

struct SAM {
  struct Node {
    int fa, len;
    int ch[10];
  } node[N];
  int q[N];
  int tr[N][26], idx = 1;
  int last = 1, tot = 1;
  int pos[N];
  int ch[N], fa[N];
  
  void insert() {
    string s;
    cin >> s;
    int p = 1;
    for (int i = 0; s[i]; i++) {
      int u = s[i] - '0';
      if (!tr[p][u]) {
        tr[p][u] = ++idx;
        fa[idx] = p;
        ch[idx] = u;
      }
      p = tr[p][u];
    }
  }
  
  int extend(int c, int last) {
    int p = last, np = ++tot;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else {
      int q = node[p].ch[c];
      if (node[q].len == node[p].len + 1) node[np].fa = q;
      else {
        int nq = ++tot;
        node[nq] = node[q], node[nq].len = node[p].len + 1;
        node[q].fa = node[np].fa = nq;
        for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
      } 
    }
    return np;
  }
  
  void build() {
    int tt = -1, hh = 0;
    for (int i = 0; i < 10; i++)
      if (tr[1][i]) q[++tt] = tr[1][i];
    pos[1] = 1;
    while (hh <= tt) {
      int t = q[hh++];
      pos[t] = extend(ch[t], pos[fa[t]]);
      for (int i = 0; i < 10; i++)
        if (tr[t][i]) q[++tt] = tr[t][i];
    }
  }
  
  int f[N], g[N];
  int din[N];

  
  int solve() {
    int res = 0;
    for (int i = 1; i <= tot; i++) {
      for (int j = 0; j < 10; j++) {
        din[node[i].ch[j]]++;
      }
    } 
    g[1] = 1;
    int tt = -1, hh = 0;
    q[++tt] = 1;
    while (hh <= tt) {
      int t = q[hh++];
      (res += f[t]) %= mod;
      for (int j = 0; j < 10; j++) {
        int v = node[t].ch[j];
        if (!v) continue;
        (g[v] += g[t]) %= mod;
        (f[v] += 10ll * f[t] % mod + 1ll * g[t] * j % mod) %= mod;
        if (!--din[v]) q[++tt] = v;
      }
    }
    return res;
  }
} sam;


int main() {
  int n;
  cin >> n;
  while (n--) sam.insert();
  sam.build();
  cout << sam.solve();
  return 0;
}

C++(clang++11) 解法, 执行用时: 324ms, 内存消耗: 99400K, 提交时间: 2020-11-19 12:14:07

#include <bits/stdc++.h>
using namespace std;


#define ll long long
const int N = 2e6 + 100;
const ll mod = 1e9 + 7;
int t[N << 1][10], fa[N << 1], len[N << 1];
int lst, cnt = 1;
void insert(int x) {
	int p = lst;
	if (t[p][x] && len[p] + 1 == len[t[p][x]]) {
		lst = t[p][x];
		return ;
	}
	int now = ++cnt;
	lst = now;
	len[now] = len[p] + 1;
	for (; p && t[p][x] == 0; p = fa[p])
		t[p][x] = now;
	if (p == 0)
		fa[now] = 1;
	else {
		int q = t[p][x];
		if (len[q] == len[p] + 1)
			fa[now] = q;
		else {
			int nq = ++cnt;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q];
			memcpy(t[nq], t[q], sizeof t[q]);
			fa[now] = fa[q] = nq;
			for (; p && t[p][x] == q; p = fa[p])
				t[p][x] = nq;
		}
	}
}

int c[N], id[N];
void top() {
	for (int i = 1; i <= cnt; i++)
		c[len[i]]++;
	for (int i = 1; i <= cnt; i++)
		c[i] += c[i - 1];
	for (int i = cnt; i >= 1; i--)
		id[c[len[i]]--] = i;
}


ll dp[N << 1], ans[N << 1];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		lst = 1;
		int len = s.size();
		for (int i = 0; i < len; i++)
			insert(s[i] - '0');
	}
	top();

	dp[1] = 1;

	for (int i = 1; i <= cnt; i++) {
		for (int j = 0; j <= 9; j++) {
			if (t[id[i]][j] == 0)
				continue;
			int now = t[id[i]][j];
			ans[now] = (ans[now] + ans[id[i]] * 10 + dp[id[i]] * j % mod) % mod;
			dp[now] = (dp[now] + dp[id[i]]) % mod;
		}
	}
	ll res = 0;
	for (int i = 1; i <= cnt; i++) {
		res = (res + ans[i]) % mod;
	}
	cout << res << endl;
	return 0;
}