Độ Dài Đoạn Chung Dài Nhất · canuc80k6215

Cho hai xâu chữ thường $A$ và $B$ . Một đoạn chung là một xâu xuất hiện liên tiếp trong cả $A$ lẫn $B$ . Hãy tìm độ dài lớn nhất của một đoạn chung.

Khác với dãy con, các ký tự của đoạn được chọn phải nằm ở những vị trí liên tiếp trong mỗi xâu. Nếu hai xâu không có ký tự chung, đáp án bằng $0$ .

Input

Dòng thứ nhất chứa xâu $A$ .
Dòng thứ hai chứa xâu $B$ .

Output

In một số nguyên: độ dài của đoạn chung dài nhất của $A$ và $B$ .

Constraints

$1 \leq ∣ A ∣, ∣ B ∣ \leq 2.5 \cdot 1 0^{5}$ .
Mỗi xâu chỉ gồm các chữ cái thường $a, \dots, z$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $∣ A ∣, ∣ B ∣ \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

abacaba
zzacabx

Output

Giải thích: Xâu acab có độ dài $4$ và xuất hiện liên tiếp trong cả hai xâu; không có đoạn chung nào dài hơn.

Ý tưởng: Dựng suffix automaton của A. Khi quét từng ký tự của B, trạng thái hiện tại mô tả hậu tố dài nhất của phần đã quét cũng là xâu con của A. Nếu thiếu transition, lùi qua suffix link cho đến khi tìm được transition phù hợp hoặc về gốc; đồng thời co độ dài đang khớp về giới hạn của trạng thái mới. Giá trị lớn nhất trong suốt quá trình là đáp án.
Ý tưởng: Mỗi lần lùi suffix link làm giảm độ dài trạng thái, nên tổng thời gian là O(|A| + |B|). Automaton có không quá 2|A|-1 trạng thái và dùng O(|A|) bộ nhớ với bảng 26 chữ cái.