String Reconstruction

题目描述

Ivan had string $s$ consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string $s$. Ivan preferred making a new string to finding the old one.

Ivan knows some information about the string $s$. Namely, he remembers, that string $t_i$ occurs in string $s$ at least $k_i$ times or more, he also remembers exactly $k_i$ positions where the string $t_i$ occurs in string $s$: these positions are $x_{i, 1}, x_{i, 2}, \ldots, x_{i, k_i}$. He remembers $n$ such strings $t_i$.

You are to reconstruct lexicographically minimal string $s$ such that it fits all the information Ivan remembers. Strings $t_i$ and string $s$ consist of small English letters only.

题意概述

有一个未知的字符串$s$，只知道$n$个它的子串$t_i$以及它们在$s$中出现的次数$k_i$和位置$x_{i, j}$。要求构造出字典序最小的原串。

数据范围：$1 \le n \le 10^5, \ 1 \le \sum |t_i|, \sum k_i, x_{i, j} \le 10^6$。

算法分析

建立双向链表，记录某个位置上一个未填充的位置和下一个未填充的位置。为了防止填充到一个已填充的位置上，我们将子串以位置为第一关键字从大到小排序，以长度为第二关键字从大到小排序，在填充时修改一下链表。最后若有未填充的位置则直接输出 a。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
string s[100001];
struct cons {
  int n, p;
  bool operator < (const cons &a) const {
    return p > a.p ? true : p == a.p ? s[n].length() > s[a.n].length() : false;
  }
} con[1000001];
int n, c, p, l, len, ma, top, pre[2000001], nxt[2000001];
char str[2000001];
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= 2000000; ++i) pre[i] = i - 1, nxt[i] = i + 1;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i]; scanf("%d", &c);
    for (int j = 1; j <= c; ++j) {
      scanf("%d", &p), con[++top].n = i, con[top].p = p;
    }
  }
  sort(con + 1, con + top + 1);
  for (int i = 1; i <= top; ++i) {
    if (con[i].p == con[i - 1].p) continue;
    l = len = s[con[i].n].length(), p = con[i].p;
    while (l > 0) {
      ma = max(ma, p), str[p] = s[con[i].n][len - l];
      nxt[pre[p]] = nxt[p];
      pre[nxt[p]] = pre[p];
      l -= nxt[p] - p, p = nxt[p];
    }
  }
  for (int i = 1; i <= ma; ++i) {
    if (str[i] >= 'a' && str[i] <= 'z') printf("%c", str[i]);
    else printf("a");
  }
  printf("\n");
  return 0;
}