Description

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

\(L = \text{abcdefg}, S = \{\text{de}\}\), 如果 BX 选择将 “de”“从 \(L\) 中删去, 则删后的 \(L = \text{abcfg}\). 现在 BX 可以进行任意多次操作 (删的次数, 顺序都随意), 他想知道最后 \(L\) 串的最短长度是多少.

Input

输入的第一行包含一个字符串, 表示 \(L\);

第二行包含一个数字 \(n\), 表示集合 \(S\) 中元素个数;

以下 \(n\) 行, 每行一个字符串, 表示 \(S\) 中的一个元素. 输入字符串都只包含小写字母.

Output

输出一个整数, 表示 \(L\) 的最短长度.

Sample Input

aaabccd
3
ac
abc
aaa

Sample Output

2

Data Range

对于 100% 的数据, 满足:\(|L| \lt 151, |S| \lt 31, \forall p \in S, |P| \lt 21\)

Explanation

令 \(dp[i][j][k][l]\) 表示母串中左端点为 \(i\), 右端点为 \(j\), 能否删到只剩下第 \(k\) 个字符串的前 \(l\) 位,\(ok[i][j]\) 表示母串 \(i-j\) 能否删完, 显然有 \(ok[i][j] = \bigcup dp[i][j][k][len[k]]\). 两种情况转移一下即可.

注意 \(dp[i][j][k][l]\) 为 bool 且 \(l\) 只有 \(21\) 位于是可以把最后一位压起来可以快 很多.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define bin(_x) (1<<(_x))
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define per(_var,_end,_begin) for(int _var=_end;_var>=_begin;_var--)
using namespace std;
typedef long long lli;
const int maxm = 155, maxn = 35, maxs = 25;

int m, n;
char str[maxm], s[maxn][maxs];
int len[maxn], occur[maxm][maxn],
    dp[maxm][maxn], f[maxm];
bool ok[maxm][maxm];

int main(int argc, char** argv)
{
    scanf("%s", str + 1);
    m = strlen(str + 1);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        len[i] = strlen(s[i] + 1);
    }
    // Dynamic programming, setting initial states
    rep(i, 1, m) rep(j, 1, n) rep(k, 1, len[j])
        if (str[i] == s[j][k])
            occur[i][j] |= bin(k);
    // Converting functions, O(n*m^2)
    per(i, m, 1) {
        rep(j, 1, n) dp[i-1][j] = 1;
        rep(j, i, m) rep(k, 1, n) {
            // Had this place ever occured
            dp[j][k] = (dp[j-1][k] << 1) & occur[j][k];
            // Using other finished strings
            rep(x, i, j-1) if (ok[x+1][j])
                dp[j][k] |= dp[x][k];
            // Finished dynamic programming this string
            if (dp[j][k] & bin(len[k]))
                ok[i][j] = true;
        }
    }
    // Last process, O(n^2)
    rep(i, 1, m) {
        f[i] = f[i-1] + 1;
        rep(j, 1, i) if (ok[j][i])
            f[i] = min(f[i], f[j-1]);
    }
    int res = f[m];
    printf("%d", f[m]);
    return 0;
}