描述

给定一个母串S,和一个串的集合 P=\left \{ t1,t2,t3... \right \},T=\left | P \right |,

定义一个串 可以与S匹配,当且仅当至多修改1个字符就可以成为S的一个子串。

输入格式

第一行一个串,表示S

第二行给出一个整数T。

接下来T行,每行一个字符串,表示ti。

输入数据保证都是英文字母(大小写都有)

输出格式

输出共T行

第i行表示ti是否可以与S匹配,如果可以输出0,否则输出1

样例输入

includestdioorzcljqmdwdgshptyetc

6

includecstring

intmain

intab

scanfddab

printfddab

returnzero

样例输出

1

1

1

1

1

1

 

数据范围与约定

  T L P 数据特点
对于10%的数据 [1,20] [1,20] [1,200] 同下
对于30%的数据 [1,200] [1,10000] [1,10000] 所有的子串长度不大于母串
对于60%的数据 [1,10000] [1,10000] [1,100000] 同上
对于100%的数据 [1,100000] [1,500000] [1,500000] 同上
 L是母串长,P是子串总长度

题目来源

原创By XTC