Dəyirmi sözlər

Son zamanlarda baş verən apokalipsisdən sonra Azamat nəhayət ki, ən uzun ümumi alt ardıcıllığın tapılması alqoritmini (LCS - longest common subsequence) öyrəndi və dərhal maraqlandı: əgər sözlər dairəvi olsa, alqoritm necə işləyəcək?

Dairəvi sözlərdə hansı simvoldan başlayaraq və hansı istiqamətdə oxunduğu önəmli deyil. Məsələn, algorithm sözü rithmalgo və oglamhtir kimi oxuna bilər.

Əgər adi formada algorithm və grammar sözləri üçün ən uzun ümumi alt ardıcıllığın uzunluğu 3-dür (söz grm), dairəvi variantda bu sözlər üçün ən uzun ümumi alt ardıcıllığın uzunluğu 4-dür (söz grma).

Azamat tez bir zamanda əmin oldu ki, məlum alqoritm dairəvi sözlər üçün düzgün cavab verə bilmir. Bu işi görəcək bir proqram yazın.

Giriş məlumatları

İki sətirdə hər biri bir söz olmaqla verilir. Sözlər boş deyil və hər birinin uzunluğu 2000 simvoldan çox deyil.

Çıxış məlumatları

Verilən dairəvi sözlərin ən uzun ümumi alt ardıcıllığının uzunluğunu göstərən bir tam ədəd çıxarın.