Schnittpunkt minimaler zyklischer Verschiebungen

C++ Hard strings

Aufgabe «Schnittpunkt minimaler zyklischer Verschiebungen»

Gegeben sind zwei Zeichenketten s und t, bestehend aus Kleinbuchstaben des lateinischen Alphabets. Es ist die Länge der längsten gemeinsamen Teilzeichenkette zu finden, die eine Teilzeichenkette einer zyklischen Verschiebung der Zeichenkette s und einer zyklischen Verschiebung der Zeichenkette t ist. Eine zyklische Verschiebung ist eine Umordnung der Zeichen einer Zeichenkette, bei der alle Zeichen um k Positionen nach links verschoben werden und die links herausfallenden Zeichen an das Ende angehängt werden. Die Länge der Zeichenketten überschreitet 10^5 nicht. Wenn keine gemeinsame Teilzeichenkette gefunden wird, geben Sie 0 aus.

Eingabeformat

In der ersten Zeile ist die Zeichenkette s (1 ≤ |s| ≤ 10^5) gegeben. In der zweiten Zeile ist die Zeichenkette t (1 ≤ |t| ≤ 10^5) gegeben. Die Zeichenketten bestehen nur aus Kleinbuchstaben des lateinischen Alphabets.

Ausgabeformat

Geben Sie eine einzelne ganze Zahl aus — die Länge der längsten gemeinsamen Teilzeichenkette, die in einer zyklischen Verschiebung von s und einer zyklischen Verschiebung von t vorkommt.

Beispiele

Beispiel 1

EINGABE

abc
def

AUSGABE

0

Beispiel 2

EINGABE

bcd

AUSGABE

abc

main.cpp