#Paho13. 【例题3】前缀匹配

【例题3】前缀匹配

【例题3】前缀匹配

题目描述

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

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

输入格式

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

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

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

输出格式

输出有M行。

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

数据范围

(原站未提供,导入后需人工补齐)

样例

7 3
SNNSSNS
NNSS
NNN
WSEE
4
2
0

提示

对于全部数据,1<=N<=107,1<=M<=1051<=N<=10^7,1<=M<=10^5,保证每一个查询串的长度均小于等于100。