# 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.

## 代码

#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;
}


418 I'm a teapot