Задача №115166. Уникальная песня
Девочка Юля захотела написать песню, чтобы попасть в чарты и реки. Но, к сожалению, у неё нет музыкального таланта, зато есть идея.
Она взяла \(n\) строк из песен своей любимой группы «ABACABA» и \(n\) строк из репертуара Алёны Фин и хочет сделать из них свою песню. Для этого она будет чередовать строки разных исполнителей. Чтобы её не обвинили в плагиате, строки \(1, 3, \ldots, 2n-1\) будут взяты из первого набора, а строки \(2, 4, \ldots, 2n\) — из второго.
Назовём уровнем рифмы двух строк длину общего суффикса этих двух строк (то есть уровнем рифмы строк \(a\) и \(b\) называется максимальное число \(r\) такое, что \(r \le |a|, r \le |b|\) и для всех \(0 \le i \le r - 1\) выполняется \(a_{|a|-i} = b_{|b|-i}\)). Музыкальностью песни называется сумма уровней рифмы пар строк \(1\) и \(2\), \(3\) и \(4\), \(\ldots\), \(2n-1\) и \(2n\) (то есть каждая строка участвует ровно в одной паре).
Помогите Юле написать хит — песню с максимальной музыкальностью!
В первой строке находится одно число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — длина наборов. В последующих \(n\) строках содержатся элементы первого набора. В последующих \(n\) строках содержатся элементы второго набора.
Все строки состоят из строчных латинских букв. Гарантируется, что сумма длин строк в каждом наборе не превосходит \(2 \cdot 10^5\).
Выведите одно число — максимальную музыкальность песни, которую можно получить.
В первом примере можно разбить строки на пары так: «dcb» + «fea», «dc a » + «fe a », «c ba » + «a ba », « bbb » + « bbb » (общие суффиксы в каждой паре выделены жирным). Сумма длин общих суффиксов равна \(0 + 1 + 2 + 3 = 6\).
4 dca cba dcb bbb fea fea aba bbb
6
3 a bc bcaa aa aaa aaac
4