【例题3】前缀匹配

题目描述

有一个长度为$N$的字符串，我们称之为母串。给定$M$个查询串。求对于每一个查询串，其前缀在母串上的最大匹配长度是多少呢？

字符串与查询串均由$E$，$S$，$W$，$N$四种字母组成。

输入格式

第一行有两个整数$N$和$M$，分别表示母串的长度和文字段的个数；

第二行是一个长度为$N$的字符串，所有字符都是$E$，$S$，$W$和$N$中的一个；

之后$M$行，每行有一个查询串。依然满足，所有字符都是$E$，$S$，$W$和$N$中的一个。

输出格式

输出有$M$行。

每一行输出一个数，表示查询串的前缀与母串的最大匹配串长度。

数据范围与提示

对于全部数据，$1 \leq N \leq 10^7$，$1 \leq M \leq 10^5$，保证每一个查询串的长度均小于等于$100$。

样例

7 3
SNNSSNS
NNSS
NNN
WSEE

4
2
0