题目描述
有一个很长的由小写字母组成的字符串。为了便于对这个字符串进行分析,需要将它划分成若干部分,每部分称为一个单词。出于减少分析量的目的,希望划分出的单词数越少越好。
输入格式
第1行1个字符串,长度不超过100。
第2行1个格数n,表示单词的个数,n≤100。
第3~n+2行,每行列出1个单词。
输出格式
一行一个正整数,表示字符串可以被划分成的最少的单词数。
样例数据
input
realityour
5
real
reality
it
your
our
output
2
样例说明
原字符串可拆成real+it+your或reality+our,由于reality+our仅为两部分,因此最优解为2。另外请注意,单词列表中的每个单词都可以重复使用多次,也可以不用。
数据规模与约定
时间限制:$1 \text{s}$
空间限制:$64 \text{MB}$