問題文
高桥的公司有一个秘密保险箱。这个保险箱有密码,但高桥忘记了密码。 不过,幸运的是,我有一个密码提示,如下所示:
- 密码是写在这张纸上的字符串。 s 长度 k 的任何子字符串 (*)。
高桥可以通过尝试所有可能的密码来打开保险箱!我很高兴。 但字符串 s 可能很长,并且字符串可能包含多个相同的子字符串。 s 也可能存在。显然,没有必要反复尝试重复的密码。 因此,我决定在手动尝试所有密码之前计算需要尝试多少个不同的密码。
你的工作是创建一个字符串 给定 s 的内容,任务是告诉高桥他需要尝试多少个不同的密码。
(※)文字列 s 的“子字符串”是一个字符串
从 s 中包含的某个区间中提取的字符串。
例如,
作为abc 的子字符串
示例包括 a,b,c,ab,bc,abc 。
ac 呀
请注意,类似 ba 的内容不是子字符串。
入力
输入是按以下格式从标准输入给出的。
s k
- 1 提示纸上写的字符串是 s (1≦|s|≦300) 。s 是一个小写字母 (
仅
a-z)。|s| 是一个字符串 表示 s 的长度。 - 2 行包含一个可用作密码的整数。 可能大于 k (1≦k≦300) 。 k 是 |s| 。
出力
输出应按以下格式执行到标准输出。 在
1 行上,输出可能的密码字符串的数量。不要忘记最后的换行符。
入力例1
abcabc 2
出力例1
3
可用作密码的子字符串集合是 {ab,bc,ca}。
入力例2
aaaaa 1
出力例2
1
密码的可能子字符串是:
仅a 。
入力例3
hello 10
出力例3
0