#P1462. Superkmp

Superkmp

题目描述

本站恢复版:给定长度为 nn 的整数序列 AA 和长度为 mm 的整数序列 BB,在 BB 中寻找与 AA 长度相同、相对大小关系相同的连续子段。

两个等长序列相对大小关系相同,是指任意两个位置的小于、等于或大于关系都一致;相等元素的对应关系也必须保留。

若存在,输出最早匹配子段在 BB 中的起点 kk,起点从 00 开始编号。否则输出 no solution!。

输入格式

第1行有一个 TT。表示一共有 TT 组数据。 每个数据的描述如下: 首先 22 个数 n,mn,m。然后 nn 个数,描述 AA 数列,接下来 mm 个数,描述 BB 数列。

输出格式

一行对应一个数据。 如果有解,输出 kk。否则输出no solution!

2
5 9
1 1 1 1 1
2 2 2 2 1 1 1 1 1
4 6
1 2 3 2
1 3 5 7 6 4
4
no solution!

提示

$1\leq T\leq 10。 1\leq N\leq 10000。 1\leq M\leq 100000$。

本站数据版本约定

保证 n≤mn\le m,所有序列元素均为 11 到 1616 的整数。本题恢复内容来自当前参考实现、原始样例与全部原数据,不冒称已找回缺失的官方原文。