P5329 [SNOI2019] 字符串 题解

Description

给出一个长度为 \(n\) 的由小写字母组成的字符串 \(a\)，设其中第 \(i\) 个字符为 \(a_i\ (1\leq i\leq n)\)。

设删掉第 \(i\) 个字符之后得到的字符串为 \(s_i\)，请按照字典序对 \(s_1,s_2,……,s_n\) 从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

Solution

容易发现对于一个极长的字符相等的连续段删掉任何一个字符都是一样的，所以先把这些连续段缩掉。

然后从前往后扫，如果 \(s_i<s_{i+1}\)，则 \(i\) 一定比 \([i+1,n]\) 的所有数字典序大，就放到末尾。否则 \(i\) 一定比 \([i+1,n]\) 的所有数字典序小，放到开头。

时间复杂度：\(O(n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

using u64 = uint64_t;

const int kMaxN = 1e5 + 5, kMaxL = 1e6 + 5, kMod = 1e9 + 7;

int n;
int len[kMaxL], sum[kMaxL];
u64 pw[kMaxL];
std::string s[kMaxN];
std::vector<int> id[kMaxN], f[kMaxN];
std::vector<u64> hs[kMaxN];

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void prework() {
  pw[0] = 1;
  for (int i = 1; i <= 1e6; ++i) pw[i] = 13331ull * pw[i - 1];
  for (int i = 1; i <= n; ++i) {
    hs[i].resize(len[i] + 1);
    for (int j = 1; j <= len[i]; ++j)
      hs[i][j] = 13331ull * hs[i][j - 1] + s[i][j];
  }
}

int getpos(int x, int p) { // 去掉 p 后第 x 个字符的位置
  if (x < p) return x;
  else return x + 1;
}

u64 gethash(std::vector<u64> &hs, int l, int r) {
  return hs[r] - hs[l - 1] * pw[r - l + 1];
}

u64 gethash(std::vector<u64> &hs, int l, int r, int p) { // [l, r] 去掉 p 的哈希值
  if (p < l || p > r) return gethash(hs, l, r);
  else return gethash(hs, l, p - 1) * pw[r - p] + gethash(hs, p + 1, r);
}

bool cmp(int a1, int b1, int a2, int b2) { // s[a1] 去掉 b1 位置的字符是否 <= s[a2] 去掉 b2 位置的字符
  int L = 0, R = std::min(len[a1] - 1, len[a2] - 1) + 1, res = 0;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (gethash(hs[a1], 1, getpos(mid, b1), b1) == gethash(hs[a2], 1, getpos(mid, b2), b2)) L = res = mid;
    else R = mid;
  }
  if (res == std::min(len[a1] - 1, len[a2] - 1)) {
    if (res == len[a1] - 1) return 1;
    else return s[a1][getpos(res + 1, b1)] == '.';
  } else {
    return s[a1][getpos(res + 1, b1)] <= s[a2][getpos(res + 1, b2)];
  }
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> s[i];
    s[i] = " " + s[i] + ".";
    len[i] = (int)s[i].size() - 1;
  }
  prework();
  for (int i = 1; i <= n; ++i) {
    id[i].resize(len[i] + 1);
    int l = 1, r = len[i], lst = 0;
    for (int j = 1; j <= len[i] - 1; ++j) {
      if (s[i][j] < s[i][j + 1]) {
        for (int k = j; k >= lst + 1; --k) id[i][r--] = k;
        lst = j;
      } else if (s[i][j] > s[i][j + 1]) {
        for (int k = lst + 1; k <= j; ++k) id[i][l++] = k;
        lst = j;
      }
    }
    for (int j = lst + 1; j <= len[i]; ++j) id[i][l++] = j;
  }
  f[1].resize(len[1] + 1);
  for (int i = 1; i <= len[1]; ++i) f[1][i] = 1;
  for (int i = 2; i <= n; ++i) {
    f[i].resize(len[i] + 1);
    for (int j = 1; j <= len[i - 1]; ++j) sum[j] = add(sum[j - 1], f[i - 1][j]);
    int p = 0;
    for (int j = 1; j <= len[i]; ++j) {
      for (; p < len[i - 1] && cmp(i - 1, id[i - 1][p + 1], i, id[i][j]); ++p) {}
      f[i][j] = sum[p];
    }
  }
  int ans = 0;
  for (int i = 1; i <= len[n]; ++i) inc(ans, f[n][i]);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}