E - Joining of DNA Sequences Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君はバイオインフォマティクスの研究をしています。ある日、2つのDNA断片を接合する作業を行うことになりました。

研究で扱うDNA断片は、塩基配列を 0 と 1 の2値で符号化した文字列として表されています。断片 S は長さ L の文字列、断片 T は長さ M の文字列です（ L \leq M ）。高橋君は、断片 S を断片 T の左側に付けるか右側に付けるかして接合したいと考えています。接合の際、2つの断片の端同士が重なるように配置できますが、重なった部分の配列は完全に一致していなければなりません。なお、重なりのない単純な連結は許されず、必ず 1 文字以上の重なりが必要です。

より正確に述べます。

左側接合（接合後の並びが S, T の順になるもの）：ある正の整数 k（ 1 \le k \le L ）を選びます。S の末尾 k 文字と T の先頭 k 文字が一致するとき、重なり幅 k で左側接合ができます。接合後の文字列は、S 全体に続けて T の先頭 k 文字を除いた残りを並べたもの（equivalently、S の先頭 L - k 文字に続けて T 全体を並べたもの）となり、全体の長さは L + M - k です。

右側接合（接合後の並びが T, S の順になるもの）：ある正の整数 k（ 1 \le k \le L ）を選びます。T の末尾 k 文字と S の先頭 k 文字が一致するとき、重なり幅 k で右側接合ができます。接合後の文字列は、T 全体に続けて S の先頭 k 文字を除いた残りを並べたもの（equivalently、T 全体に続けて S の末尾 L - k 文字を並べたもの）となり、全体の長さは L + M - k です。

いずれの場合も k = L（S 全体が T の端と重なる場合）も許されます。L \leq M であるため、k \le L の範囲では T 側にも k 文字以上が常に存在することに注意してください。

重なり幅が大きいほど接合後の全体の長さが短くなり、解析が効率的になります。高橋君は、左側接合・右側接合のいずれかを選んで、重なり幅を最大化したいと考えています。

左側接合で実現可能な最大の重なり幅と、右側接合で実現可能な最大の重なり幅のうち、大きい方の値を求めてください。どちらの接合方法でも重なり幅 1 以上の接合が不可能な場合（すなわち、左側接合でも右側接合でも配列が一致する重なりが存在しない場合）は、0 を出力してください。

制約

  • 1 \leq L \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • L \leq M
  • S は長さ L の文字列であり、0 と 1 のみからなる。
  • T は長さ M の文字列であり、0 と 1 のみからなる。

入力

L M
S
T
  • 1 行目には、断片 S の長さ L と、断片 T の長さ M が、スペース区切りで与えられる。
  • 2 行目には、断片 S を表す長さ L の文字列が与えられる。S は 0 と 1 のみからなる。
  • 3 行目には、断片 T を表す長さ M の文字列が与えられる。T は 0 と 1 のみからなる。

出力

左側接合および右側接合で実現可能な最大の重なり幅のうち、大きい方の値を 1 行で出力せよ。どちらの接合方法でも重なり幅 1 以上の接合が不可能な場合は 0 を出力せよ。

入力例 1

3 5
101
01101

出力例 1

3

入力例 2

1 4
0
1111

出力例 2

0

入力例 3

12 20
110010101011
01010110011101011010

出力例 3

7

入力例 4

50 80
01001101010100110101010011010101001101010100110101
01001101010100110101010011010111111000001111100000111110000011111000001111100000

出力例 4

30

入力例 5

1 1
1
1

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is conducting research in bioinformatics. One day, he needs to join two DNA fragments together.

The DNA fragments used in the research are represented as strings where the base sequences are encoded using the two values 0 and 1. Fragment S is a string of length L, and fragment T is a string of length M (L \leq M). Takahashi wants to join fragment S to either the left side or the right side of fragment T. During joining, the ends of the two fragments can be placed so that they overlap, but the sequences in the overlapping portion must match exactly. Simple concatenation without overlap is not allowed; an overlap of at least 1 character is required.

More precisely:

Left joining (the resulting order is S, T): Choose a positive integer k (1 \le k \le L). When the last k characters of S match the first k characters of T, a left join with overlap width k is possible. The resulting string is formed by S in its entirety followed by the remaining part of T after removing its first k characters (equivalently, the first L - k characters of S followed by T in its entirety), and has total length L + M - k.

Right joining (the resulting order is T, S): Choose a positive integer k (1 \le k \le L). When the last k characters of T match the first k characters of S, a right join with overlap width k is possible. The resulting string is formed by T in its entirety followed by the remaining part of S after removing its first k characters (equivalently, T in its entirety followed by the last L - k characters of S), and has total length L + M - k.

In both cases, k = L (where the entirety of S overlaps with an end of T) is also permitted. Note that since L \leq M, for any k \le L, T always has at least k characters available.

The larger the overlap width, the shorter the total length after joining, making analysis more efficient. Takahashi wants to choose either left joining or right joining to maximize the overlap width.

Find the larger of the maximum achievable overlap width for left joining and the maximum achievable overlap width for right joining. If joining with an overlap width of 1 or more is impossible for both joining methods (i.e., there is no overlap where the sequences match for either left joining or right joining), output 0.

Constraints

  • 1 \leq L \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • L \leq M
  • S is a string of length L consisting only of 0 and 1.
  • T is a string of length M consisting only of 0 and 1.

Input

L M
S
T
  • The first line contains the length L of fragment S and the length M of fragment T, separated by a space.
  • The second line contains a string of length L representing fragment S. S consists only of 0 and 1.
  • The third line contains a string of length M representing fragment T. T consists only of 0 and 1.

Output

Output in a single line the larger of the maximum achievable overlap widths for left joining and right joining. If joining with an overlap width of 1 or more is impossible for both joining methods, output 0.

Sample Input 1

3 5
101
01101

Sample Output 1

3

Sample Input 2

1 4
0
1111

Sample Output 2

0

Sample Input 3

12 20
110010101011
01010110011101011010

Sample Output 3

7

Sample Input 4

50 80
01001101010100110101010011010101001101010100110101
01001101010100110101010011010111111000001111100000111110000011111000001111100000

Sample Output 4

30

Sample Input 5

1 1
1
1

Sample Output 5

1