#P3574. [Hnoi2014]抄卡组

    ID: 2773 传统题 1500ms 512MiB 尝试: 1252 已通过: 249 难度: 7 上传者: 标签>难度分类提高字符串KMP贪心贪心保持领先CF2200鸣谢NanoApe重新制作数据

[Hnoi2014]抄卡组

[HNOI2014] 抄卡组

题目描述

一天闲着无聊的小L找来了当前正火爆的游戏《炉石传说》来玩,但是怎么打怎么输,于是他大喊一声”我要抄卡组!“就找来了游戏传说组第一名的游戏高手小H的直播来看。

但是小L家的网络技术还停留在拨号,看着直播画面又是卡顿又是花屏,他不给力的网络让他完全无法记录小H展示的给力的卡组。小L周围都是学霸没有人玩游戏想去帮他这个忙,但是学霸们热衷于讨论各种信息学问题。

由于每次直播花屏的位置不同,小 L 能记录到卡组的不同片段。不过,小 H 每次展示的卡组也可能不同,小 L 想判断记录是否两两相容。

把每份记录看成一个模式串,其中通配符 * 能匹配任意长度的字符串,包括空串。若两个模式可以匹配同一个普通字符串,就称这两个模式匹配。判断给定的所有模式是否两两匹配。

输入格式

第一行一个正整数 TT,表示数据组数。每组的第一行为正整数 NN,接下来 NN 行,每行是一个只包含小写字母、数字和通配符 * 的模式串。

模式可以为空,空行表示空模式。应按行读取模式。原数据使用 UNIX 换行。

输出格式

每组输出一行一个大写字母。若所有模式两两匹配,输出 Y;否则输出 N。

样例 #1

10
2
1234567890*1234567890
1234567890a1234567890
2
1234567890*1234567890
1234567890*1234567890
2
1234*67890a1234567890
1234567890*1234567890
2
1234567890*1234567890
1234567890a12345*7890
2
1234567890*1234567890
*12345
2
12345*67890
1234567890*1234567890
2
1234567890*1234567890
12345*
2
1234567890*1234567890
*67890
2
67890*
1234567890*1234567890
2
1234567890*a*1234567890
1234567890*1234567890
Y
Y
Y
Y
N
Y
Y
Y
N
Y

数据范围

T=10T=10,N≤100000N\le100000,输入文件不超过原题所称的 10M,且 NN 与组内最长字符串长度的乘积不超过 2×1082\times10^8。