Problem : 182 - hh盜墓記

Problem Statistics

Solved Member: 7　　Submission: 58　　User Tried: 13

Statement:

在hh看完盜墓筆記後，很喜歡主角天真無邪與胖子與悶油瓶小哥在古墓的歷險，因此帶了他收服的龍前往他們去過的古墓。

書中都說要準備黑驢子蹄，以防有粽子突然蹦蹦蹦地跳出咬你，但hh並不需要，他有的是觸手與龍可以幫他對付「血劇死」(一種血粽子的進化版本，喜歡用觸手攻擊路過的盜墓者)，於是hh很開心的帶著他的龍出發了。

古墓裡有許多機關，但在魔法威能的龍使面前都不堪一擊，直到出現了一個散發出神秘力量氣息的門，這是一扇用什麼魔法都無法摧毀的門。

想得到我的祕寶嗎，去追尋吧，我全都放到門的後面。
注：要打開這扇門就要解開此密碼。

門上突然顯現出這幾個字。

之後便出現一串長度為N，全由小寫英文字母所組成的字串S，接著眼前也出現了M個字串卡，奇怪的是每種字串卡怎麼拿也拿不完，看來被施了很強大的魔法，莫非這裡是... ...

此時神秘男子的聲音再度響起。

想通過這扇門，就先破解密碼吧！一個字串卡Li如果是S的子字串，便能覆蓋那段區間，當你把所有可能被覆蓋的字母覆蓋後，密碼就出來了...

這應該是那位偉大的龍使弗利茲的棺木吧！喔喔喔，這真是令人興奮的一件事，請你幫hh解出密碼吧！

Input:Output:

第一行有一個數字N ( 1 ≤ N ≤ 300000 )
第二行有一長度為N的字串S
第三行有一個數字M ( 1 ≤ M ≤ 5000 )
接下來M行，每行一個字串Li，其中長度不超過5000

請輸出一個數字代表密碼長度。

Sample Input:Sample Output:

Sample A:
6
abcbab
2
cb
cbab

Sample B:
4
abab
2
bac
baba

Sample C:
6
abcabc
2
abca
cab

Sample A:
2

Sample B:
4

Sample C:
1

HINT:

最後hh解出的密碼在經過一連串加密後是 7122
hh興奮得進去後，發現裡面一無所有... so sad...
前往下一個目的地 (?)

Source:

COCI 2011/2012 #5

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	500ms	524288kb
0-2	500ms	524288kb
0-3	500ms	524288kb
1	500ms	524288kb	8
2	500ms	524288kb	8
3	1000ms	524288kb	8
4-1	1500ms	524288kb	14
4-2	1500ms	524288kb
5-1	1500ms	524288kb	14
5-2	1500ms	524288kb
6-1	8000ms	524288kb	16
6-2	12000ms	524288kb
6-3	10000ms	524288kb
6-4	8000ms	524288kb
7-1	8000ms	524288kb	16
7-2	12000ms	524288kb
7-3	10000ms	524288kb
7-4	8000ms	524288kb
8-1	8000ms	524288kb	16
8-2	12000ms	524288kb
8-3	10000ms	524288kb
8-4	8000ms	524288kb