《AC自动机模板题》
#include <bits/stdc++.h>
using namespace std;
int edge[505][200], fail[505], fa[505], r[505], len[505], f[2000005];
string s[200005], t;
char v[505], tx[2000005];
int n, top, m;
queue<int> q;
bool vis[505];
inline void read(string &s) {
s = "";
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
while (c >= 'a' && c <= 'z')
s += c, c = getchar();
}
void write(int x) {
if(x>9) write(x/10);
putchar(x % 10 + '0');
}
int main() {
read(t);
cin >> n;
for (int i = 1; i <= n; i++)
read(s[i]);
for (int i = 1; i <= n; i++) {
int now = 0;
for (int j = 0; j < s[i].size(); j++) {
if (!edge[now][s[i][j]]) // 建边
edge[now][s[i][j]] = ++top, fa[top] = now; // 建立节点
now = edge[now][s[i][j]];
if (j + 1 == s[i].size())
len[now] = s[i].size();
v[now] = s[i][j];
}
}
q.push(0);
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = 'a'; i <= 'z'; i ++)
if (edge[f][i])
q.push(edge[f][i]);
if (fa[f] != 0) {
int tmp = fail[fa[f]];
fail[f] = edge[tmp][v[f]];
r[fail[f]]++;
//cout << "Fail[" << f << "]" << " is " << fail[f] << endl;
}
for(int i = 'a'; i <= 'z'; i ++)
if(!edge[f][i])
edge[f][i] = edge[fail[f]][i];
}
int now = 0;
for(int i = 0;i < t.size();i ++) {
now = edge[now][t[i]];
int tnow = now;
f[i] = 114514;
while(tnow)
f[i] = min(f[i], f[i - len[tnow]] + 1),tnow = fail[tnow];
}
cout << f[t.size() - 1];
return 0;
}