seuOJ365 - 斐波那契字符串

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：512 MiB
• 题目标签：冬季, 校赛, 初赛, 2021

题目描述

给定两个字符串 $S_0,S_1$。

对于 $n>1$，定义 $S_n=S_{n-2}+S_{n-1}$，其中 + 表示拼接操作。

求出 $S_n$ 中包含的 $T$ 串个数。

输入格式

第一行三个字符串 $S_0,S_1,T$，用空格隔开。

然后一行一个整数 $n$ 。

输出格式

输出一行一个整数表示答案。

样例

样例输入1

AC AC AC
3

样例输出1

3

样例输入2

ACA CB AC
2

样例输出2

2

数据范围与提示

用 $|S|$ 表示字符串 $S$ 的长度。

$1\leq |S_0|,|S_1|\leq 100,|T|=2,0\leq n\leq 60$，字符串只包含大写字母。