TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1367
  • 题目
  • P1367【COCI 2011/2012 CONTEST #5-6】覆盖字符串
    限制 : 时间限制 : 40000 MS   空间限制 : 512000 KB
    评测说明 : 2s
    问题描述

    给出一个长度为N的小写字母串,现在Mirko有M个若干长度为Li的小写字符串。Mirko要用这M个字符串去覆盖给出的那个字符串的。覆盖时,必须保证:

    1.Mirko的字符串不能拆开,旋转;

    2.Mirko的字符串必须和给出的字符串的某一连续段完全一致才能覆盖,

    3.若干次覆盖可以部分重叠

    4.Mirko的字符串可以无限使用。

    求给出的字符串当中,有多少个字母是无法覆盖的。

    输入格式

    第1行:1个正整数N(1 ≤ N ≤ 300 000),表示单词的总数

    第2行:N个小写英文字母,表示给出的字符串。
    第3行:1个正整数M(1 ≤ M ≤ 5000),表示用来覆盖的字符串。
    接下来M行,每行1个字符串,长度为Li(1 ≤ Li ≤ 5000),字符串均由小写字母组成

    输出格式

    第1行:1个整数,表示无法被覆盖的字符个数

    样例输入

    6
    abcabc
    2
    abca
    cab

    样例输出

    1