問題文
你从你的朋友拓哉那里收到了一个用独特方法压缩的字符串,以及解压后要引用的部分的位置和长度。
需要创建一个程序来获取要引用的部分的字符串。
压缩前的字符串是仅由字母字符组成的字符串。
以及仅由字母字符组成的子字符串
重复 x 是
在 n 次的部分
通过替换为 (x)n 进行压缩。
但是,
运算前设定中包含的|x| \geq 1、n \geq 1 。 ( |x| 是
您也可以写 x 字符串长度 )
例如, ABABABA 是
您也可以写 (AB)3A 替换。
此外,该替换操作可以执行任意多次。
替换为
例如,AAABBAAABB 是
您也可以写 (AAABB)2 后,此外,
可以替换为((A)3BB)2 、 ((A)3(B)2)2 。
由上可知,压缩后的字符串( 输入 )如下EBNF 遵循。
input = string,{string} ;
string = alphabet,{alphabet} | "(",input,")",positive_number ;
alphabet = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" |
"N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" |
"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" |
"n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ;
positive_number = digit_excluding_zero,{digit} ;
digit_excluding_zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit_excluding_zero ;
入力
输入是按以下格式从标准输入给出的。
B L N S
- 1 行表示扩展后要参考的部分的起始位置。 B ( -M \leq B \lt M ) , 参考长度 L ( 1 \leq L \leq 10^5 ) , 压缩后的字符串长度 N ( 1 \leq N \leq 10^4 )以整数形式给出,并用空格分隔。 然而,M 是压缩前字符串的长度。
- 2 行包含压缩后的字符串。 S 。 表示
- B 如果非负,则从 0 表示从开始的位置,如果为负数,则表示结束 -1 表示从末尾算起的位置。
- B 是正数还是负数。 L 字符是要引用的字符串,保证得到这个长度的字符串。
- 压缩前字符串的长度为 不超过 10^{15} 。
部分点
- 压缩前字符串的长度 如果您正确回答M和 L, N \leq 100, M \leq 1000 ,您将获得 50 分(总分为 130 分)。 如果您正确回答
- L, N \leq 100 ,您将在 130 分中额外获得 50 分作为部分分。
出力
标准输出引用的字符串 1 行。
请注意,行尾需要换行。
定义
入力例 1
0 7 6 (AB)3A
出力例 1
ABABABA
入力例 2
-6 5 11 ((A)3(B)2)2
出力例 2
BAAAB