1896. [国家集训队2011]字符串游戏

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例说明】

【数据规模和约定】

【问题描述】

        BX正在进行一个字符串游戏，他手上有一个字符串L，以及其他一些字符串的集合S，然后他可以进行以下操作：对于一个在集合S中的字符串p,如果p在L中出现，BX就可以选择是否将其删除，如果删除，则将删除后L分裂成的左右两部分合并。

    举个例子，L='abcdefg' , S={'de'}，如果BX选择将'de'从L中删去，则删后的L='abcfg'。

    现在BX可以进行任意多次操作（删的次数，顺序都随意），他想知道最后L串的最短长度是多少。

【输入格式】

    输入的第一行包含一个字符串，表示L。

    第二行包含一个数字n，表示集合S中元素个数。

    以下n行，每行一个字符串，表示S中的一个元素。

    输入字符串都只包含小写字母。

【输出格式】

    输出一个整数，表示L的最短长度。

【样例输入】

    aaabccd

    3

    ac

    abc

    aaa

【样例输出】

    2

【样例说明】

    aaabccd

    aacd

    ad

【数据规模】

    对于40%数据，满足|L|<9

    对于100%数据,满足|L|<151,|S|<31,S中的每个元素|p|<21