VK Cup 2012 Раунд 3 |
---|
Закончено |
Поликарп увлекается изучением берляндских иероглифов. Как-то раз Поликарп раздобыл два древних берляндских рисунка, на каждом из которых была нарисована окружность из иероглифов. Известно, что ни один иероглиф не встречается дважды ни в первой окружности, ни во второй (но может встречаться по одному разу в каждой из них).
Поликарп хочет записать эти изображения к себе в ноутбук, но — увы — ноутбуки не позволяют записывать иероглифы окружностями. Поэтому Поликарп вынужден разорвать каждую окружность и записать все ее иероглифы в порядке обхода по часовой стрелке в одну строку. Строку, полученную из первой окружности, будем называть a, а полученную из второй — b.
Вариантов разорвать окружности из иероглифов достаточно много, поэтому Поликарп выбирает такой способ, что длина наибольшей подстроки строки a, которая встречается как подпоследовательность в строке b, максимальна.
Помогите Поликарпу — найдите максимальную возможную длину искомой подстроки (подпоследовательности) при оптимальном разрыве первой и второй окружностей.
Длиной строки s называется количество символов в ней. Если длина строки s обозначается |s|, строку можно записать s в виде s = s1s2... s|s|.
Непустую строку x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) будем называть подстрокой строки s. Например, «code» и «force» — подстроки «codeforces», а «coders» — нет.
Непустую строку y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|) будем называть подпоследовательностью строки s. Например, «coders» — подпоследовательность «codeforces».
Первая строка содержит два целых числа la и lb (1 ≤ la, lb ≤ 1000000) — количество иероглифов в первой и второй окружности, соответственно.
Ниже из-за сложностей с кодировкой берляндские иероглифы задаются целыми числами от 1 до 106.
Вторая строка содержит la целых чисел — иероглифы на первом рисунке, в порядке обхода по часовой стрелке, начиная с одного из них.
Третья строка содержит lb целых чисел — иероглифы на втором рисунке, в порядке обхода по часовой стрелке, начиная с одного из них.
Гарантируется, что в первой окружности нет иероглифа, который встречается дважды. Вторая окружность тоже обладает этим свойством.
Выведите единственное число — наибольшую длину общей подстроки и подпоследовательности. Если при любом способе разрыва окружностей такой не существует, то выведите 0.
5 4
1 2 3 4 5
1 3 5 6
2
4 6
1 3 5 2
1 2 3 4 5 6
3
3 3
1 2 3
3 2 1
2
В первом тесте Поликарп выбирает подстроку, состоящую из иероглифов 5 и 1, во втором — из 1, 3 и 5.
Название |
---|