问题3143--2-1 我不吃牛肉

3143: 2-1 我不吃牛肉

时间限制: 1 Sec  内存限制: 256 MB
提交: 29  解决: 11
[状态] [讨论版] [提交] [命题人:]
题目描述

这一天忙碌了一上午的曹同学来到了铁牛面馆来吃面,店长李铁牛师傅十分的热情好客,当场给曹同学推荐了自己的拿手好戏:铁牛牛肉面

饥肠辘辘的曹同学十分期待李师傅的手艺,当场表示要尝一碗铁牛牛肉面,不过不能放葱花,李师傅答应了下来,立刻前往后厨下面。不一会儿,香喷喷的牛肉面便被端了上来,曹同学看到面条上满满的牛肉,而且还没有自己最讨厌的葱花,满脸愉悦,当场说道:“我爱吃牛肉!”

对于一碗香喷喷的铁牛牛肉面,其由以下材料构成:牛肉 (Beaf),葱花 (Green onion),面条 (Noodles),水 (Water),调料 (Seasoning)。

铁牛牛肉面之所以十分有名,那便是因为李师傅拥有着祖传的秘方,形式上秘方是一串全为大写字母的字符串,字符串上的字母取自以上五个材料的首个大写字母,即可代表着指定的材料,而一道正宗的铁牛牛肉面必须由长度的连续的秘方字符串的子串组成。

美味只是铁牛牛肉面远近闻名的优点之一,用料足也是一大被客人赞不绝口的优点,因此一道正宗的铁牛牛肉面需要在满足客人要求(即不存在客人忌口的材料)的情况下尽可能的用料充实,具体来说选取的字串必须是所有满足客人要求的字串中最长的。只有这样做出来的铁牛牛肉面才是真正的好吃,实惠不愧于父老乡亲的赞誉。

聪明如你,能找到最长的满足以上条件的秘方字符串的子串长度吗?

输入

第一行输入一个整数 n (1 ≤ n ≤ 106)

第二行读入一个长度为 n 的字符串 s ( ∀si ∈ {'B', 'G', 'N', 'W', 'S'})

第三行读入一个整数 k,代表客人的忌口的数量. (0 ≤ k ≤ 5)

接下来 k 行,每行读入一个字符串表示客人忌口的材料。

输出
输出一个整数,表示最长的合法字符串子串长度。
样例输入 Copy
10
BGWSBBBBBB
1
Green onion
样例输出 Copy
8