P15835 [蓝桥杯第一届国际赛] 基因配对

题目描述

生物的基因都是由 4 种不同的碱基构成，一般用 A、T、G、C 表示这 4 种碱基。碱基之间可以配对构成碱基对，在配对时只能 A 和 T 配对，G 和 C 配对。

配对的碱基对按某种顺序连接成螺旋的梯子状，组成了基因。下面给出了一个基因的示意图。

【缺图】

一般而言，表示一个基因只需要使用一测的碱基序列即可。例如，使用 AGTC 来表示一个基因片段时，可知其对应的另一侧的基因片段是 TCAG。

现在给了一段较长的基因片段 $L$ 和一段较短的基因片段 $S$，请问基因片段 $S$ 是否能和 $L$ 中的某一段正好配对。我们说一段基因能和另一段基因配对是指这段基因中的每个碱基和另一段中对应位置的碱基配对。因碱基具有方向性，因此在配对的时候不能倒序。

例如，若 $L = \text{ATCAAAATCG}$，$S = \text{TTTAG}$，则 $S$ 能和 $L$ 中的一段正好配对，配对的段为 AAATC，它是从 $L$ 的第 4 个位置开始的。

输入格式

输入的第一行包含一个字符串，表示 $L$。

第二行包含一个字符串，表示 $S$。

$L$ 和 $S$ 都只包含 A、T、G、C 四种字符，$S$ 的长度不超过 $L$ 的长度。

输出格式

如果能配对，输出最早的配对的位置。如果不能配对，输出 0。

输入输出样例 #1

输入 #1

ATCAAATCG
TTTAG

输出 #1

4

说明/提示

评测用例规模与约定

对于 70% 的评测用例，$L$ 和 $S$ 的长度均不超过 $1000$；

对于所有评测用例，$L$ 和 $S$ 的长度均不超过 $10^6$。你可能需要使用比较快的函数才能在时限内完成比较。