研学活动中,同学们按时间顺序获得了 n 枚印章,每枚印章都有一个种类名称。老师另给出一份长度为 m 的目标名单,要求收集名单中的所有种类。
目标名单中可能重复写出同一个名称。一个种类即使在名单中出现多次,也只要求片段里至少出现一枚这种印章。记录中也可能出现不属于目标名单的印章。
小明希望从获得印章的记录中,截取一段连续的、非空的记录,使这一段包含全部目标种类,并且长度尽可能短。片段长度包括其中不属于目标名单的印章。
请输出最短片段的长度。如果整份记录都不包含全部目标种类,输出 0。
第一行包含两个整数 n,m,表示记录长度和目标名单长度。
第二行包含 m 个用空格分隔的名称,表示目标名单。
第三行包含 n 个用空格分隔的名称,按获得顺序表示印章记录。
对全部数据,1\le n,m\le200000。每个名称只含小写英文字母,长度为1到12。目标名单与印章记录都允许重复名称。
输出一个整数,表示最短合法片段长度;不存在时输出 0。
8 4 red blue red green red other blue red green blue other red
3
4 2 sun moon sun star sun cloud
0
目标种类实际上只有red、blue、green三种。第3到第5枚依次为blue、red、green,是长度3的合法片段。任何合法片段都至少需要3枚印章,因此答案为3。
记录中没有moon,不能覆盖全部目标种类。