← 返回题单

题单练习挑战赛普及/提高- 题

← 上一题下一题 →

A4760 | $串串$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

夏天到了，又到了吃串串的季节。 你的手中有两个串串。每个串串上都串了很多食材。 如果把串串上的食材看成字符，那么一个串串就相当于由一些字符组成的字符串。为了方便描述，我们把这两个串串称作字符串$A$和$B$。 现在，你想找到字符串$B$的一个最长前缀，使得这个前缀在字符串$A$中至少出现了$n$次($n\leq |A|$)。 这$n$次出现可以重叠，例如在字符串"ababa"中，"aba"出现了两次。

输入格式

第一行一个字符串$A$，只包含英文小写字母。 第二行一个字符串$B$，只包含英文小写字母。 第三行一个整数$n$，意义如题。

输出格式

输出一共一行。 如果存在$B$的最长前缀，使得这个前缀在$A$中至少出现了$n$次，则输出这个最长前缀； 否则，输出"IMPOSSIBLE"(不含引号)。

输入输出样例

输入 #1

aaaaa
aaa
4

输出 #1

aa

输入 #2

abbabbabba
abbab
3

输出 #2

abba

输入 #3

programming
unal
1

输出 #3

IMPOSSIBLE

C++ 编辑器

输入

输出