交换无名指金色的契约 / 给彼此岁月
题解
给定两个字符串 $s_1,s_2$，判断是否可以通过在 $s_1$ 的前面或某个字符后面插入一个字符串的方式将 $s_1$ 变为 $s_2$。
$T$ 组测试数据，$1 \le T \le 10,1 \le |s_1| \le |s_2| \le 10^5,1.0\rm{s},512\rm{MiB}$。
下文中，字符串的下标从 $1$ 开始，记 $s[l,r]$ 表示字符串 $s$ 删除前 $l-1$ 个字符和后 $|s|-r$ 个字符后所剩下的字符串。
令 $x=\max{i|s_1[1,i]=s_2[1,i]}$。显然，成立的充要条件是 $s_1[x+1,|s_1|]=s_2[|s_2|-|s_1|+x+1,|s_2|]$。直接模拟即可。时间复杂度 $O\left(Tn\right)$。