一份重要文件被撕成两半，其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号，如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配，最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。

图1 纸条编号

图2 还原结果

输入格式：

输入首先在第一行中给出一个正整数 N（1<N≤105），为没有切碎的半张纸上断口折线角点的个数；随后一行给出从左到右 N 个折线角点的高度值（均为不超过 100 的非负整数）。

随后一行给出一个正整数 M（≤100），为碎纸机里的纸条数量。接下去有 M 行，其中第 i 行给出编号为 i（1≤i≤M）的纸条的断口信息，格式为：

K h[1] h[2] ... h[K]

其中 K 是断口折线角点的个数（不超过 104+1），后面是从左到右 K 个折线角点的高度值。为简单起见，这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。

输出格式：

在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔，行首尾不得有多余空格。

题目数据保证存在唯一解。

输入样例：

17
95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80
6
4 68 58 58 80
3 81 68 68
3 95 70 80
3 68 60 80
5 80 72 88 81 81
4 80 97 97 68

输出样例：

3 6 1 5 2 4

题解

注意到整个拼接过程类似于模式匹配，用 68 58 58 80 举例，这一序列在原序列的第六个位置匹配上了。由于折纸的高度为不超过100的非负整数，所以可以用字符类型去存储每一个数字，博主是用string去存储的，效果是一样的。总共有$m = 100$个模式串，由$N$是$1e^{5}$，单个模式串的长度最长$k = 1e^{4}$，如果暴力匹配时间复杂度为$O(m * n * k)$一眼过不了，所以我们需要用$kmp$进行优化，将单次模式匹配的时间复杂度优化为$O(n + k)$，那么总复杂度为$O(m * (n + k))$足够通过本题。
需要注意一点的是，所有模式串中可能存在一个模式串是另一个模式串前缀的可能，就会造成两个模式串匹配到了同一个位置。例如$s = “abcab”$，$p1 = “ab”$，$p2 = “abc”$，都在第一个位置成功匹配。然后我们有如下考虑，题目保证结果唯一，那么一个模式串必然能唯一匹配到原串中的一个位置，造成匹配结果不唯一的原因是其中一个模式串是另一个模式串的前缀，如果我们按照模式串长度从大到小的顺序匹配，并且将匹配结果记录，如果另一个串匹配到同一位置就继续匹配，直到匹配到一个未被匹配的位置。

参考代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<bitset>
#include<string>
#include<cstring>

using namespace std;

bool vis[100005];

struct node{
	int id, pos, len;
	vector<string> s;
};

void getNext(vector<string> &s, vector<int> &nex){
	int n = nex.size() - 1;
	int i = 1, j = 0;
	nex[1] = 0;
	while(i < n){
		if(s[i] == s[j] || j == 0){
			i++,j++;
			nex[i] = j;
		}else j = nex[j];
	}
}

int kmp(vector<string> &s, vector<string> &p, vector<int> &nex){
	int n = s.size() - 1;
	int len = p.size() - 1;
	int i = 1, j = 1;
	int pos = -1;
	while(i <= n){
		if(j == len + 1){
			if(vis[i - len] == 0){
				pos = i - len;
				break;
			}
			j = 1;
		}
		if(s[i] == p[j] || j == 0){
			i++, j++;
		}else j = nex[j];
	}
	if(j == len + 1) pos = i - len;
	return pos;
}

void solve() {
	int n;
	cin >> n;
	vector<string> a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	int q;
	cin >> q;
	vector<node> ans(q + 1);
	for(int i = 1, x; i <= q; i++){
		cin >> x;
		ans[i].s = vector<string>(x + 1);
		ans[i].id = i;
		ans[i].len = x;
		for(int j = 1; j <= x; j++) cin >> ans[i].s[j];
	}	
	sort(ans.begin() + 1, ans.end(), [](node a, node b){
		return a.len < b.len;
	});
	for(int i = 1; i <= q; i++){
		vector<int> nex(ans[i].len + 1);
		getNext(ans[i].s, nex);
		ans[i].pos = kmp(a, ans[i].s, nex);
		vis[ans[i].pos] = 1;
	}
	sort(ans.begin() + 1, ans.end(),[](node a, node b){
		return a.pos < b.pos;	
	});
	for(int i = 1; i <= q; i++) cout << ans[i].id << " \n"[i == q];
}

int main() {
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
    return 0;
}