Problem Description

A gene is made up of 4 different kinds of bases, usually denoted by A, T, G, and C. Bases can pair to form base pairs. During pairing, only A can pair with T, and G can pair with C.

Paired base pairs are connected in a certain order to form a spiral ladder shape, which makes up a gene. An illustration of a gene is shown below.

[Image missing]

In general, to represent a gene, it is enough to use the base sequence on one side. For example, if we use AGTC to represent a gene segment, then we know the corresponding gene segment on the other side is TCAG.

Now you are given a longer gene segment $L$ and a shorter gene segment $S$. Determine whether $S$ can pair exactly with some substring of $L$. We say that one gene segment can pair with another if every base in one segment pairs with the base at the corresponding position in the other segment. Since bases have direction, you cannot reverse the order when pairing.

For example, if $L = \text{ATCAAATCG}$ and $S = \text{TTTAG}$, then $S$ can pair exactly with a substring of $L$. The paired substring is AAATC, which starts from the 4th position of $L$.

Input Format

The first line contains a string representing $L$.

The second line contains a string representing $S$.

Both $L$ and $S$ contain only the characters A, T, G, C, and the length of $S$ does not exceed the length of $L$.

Output Format

If pairing is possible, output the earliest starting position of a matching substring. If pairing is not possible, output 0.

ATCAAATCG
TTTAG

4

Hint

Constraints

For 70% of the testdata, the lengths of $L$ and $S$ are both at most $1000$.

For all testdata, the lengths of $L$ and $S$ are both at most $10^6$. You may need to use relatively fast functions to finish the comparisons within the time limit.

Translated by ChatGPT 5