D. Өндөр тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Паул Эрдос-ын таамаглал үнэнээ олжээ. Эцэст нь харийнхан дэлхий дээр газардав. Бидний төсөөлснөөс зөрүүтэй байсан зүйл нь тэд хүн төрөлхтнөөс Рамсей-ын тооны утгыг тооцоолж өгөх талаар асуусангүй (магадгүй тэд өөрсдөө уг тоог бодчихсон байх). Тэд харин Рамсей-ын тоог тооцоолохтой ижил нэгэн хүндхэн бодлогыг бодож өгөхийг хүсжээ. Түүнчлэн харийнхан хэрэв хүн төрөлхтөн уг бодлогыг 2 цагийн дотор бодохгүй бол дэлхийг устгана хэмээн сүрдүүлжээ.

Тэд уг бодлогын өгүүлбэрийг хэлэхээсээ өмнө өндөр тэмдэгт мөрийг танилцуулжээ. Өндөр тэмдэгт мөр гэдэг нь хэсэг суурь тэмдэгт мөрүүдийн хэлхээ тэмдэгт мөр юм. Танд $b_{1}, b_{2}, ..., b_{n}$ гэсэн суурь тэмдэгт мөрүүдийн бүртгэл өгөгдсөн гэж үзье. Тэгвэл $i_{1}, i_{2}, ..., i_{m}$ гэсэн индексүүдийн бүртгэлээс үүсэх өндөр тэмдэгт мөр нь $b_{i_{1}}, b_{i_{2}}, ..., b_{i_{m}}$ гэсэн суурь тэмдэгт мөрүүдийн хэлхээ тэмдэгт мөр байх ажээ. Өндөр тэмдэгт мөр нь маш том байж болох бөгөөд уг тэмдэгт мөрүүд дээр үйлдэл хийх нь компьютерт маш их ачаалал өгөх юм.

Харийнхан хүн төрөлхтнөөс өндөр тэмдэгт мөр $t$ болон тэмдэгт мөр $s$ доторх хамгийн урт ерөнхий дэд дарааллын уртыг тооцож өгөхийг хүсжээ.

Оролт

Эхний мөрөнд суурь тэмдэгт мөрийн тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 2000$) өгөгдөнө.

Дараагийн $n$ мөрөнд суурь тэмдэгт мөрүүдийн утгууд өгөгдөнө. Суурь тэмдэгт мөр болгон нь Латин жижиг үсгүүдээс тогтсон байх бөгөөд хоосон тэмдэгт мөр байж болохгүй. Түүнчлэн бүх $n$ ширхэг суурь тэмдэгт мөрүүдийн уртуудын нийлбэр нь $10^{6}$-аас хэтрэхгүй байна.

Дараагийн мөрөнд өгөгдсөн өндөр тэмдэгт мөр $t$ дотор байх суурь тэмдэгт мөрүүдийн тоог илэрхийлэх бүхэл тоо $m$ ($1 ≤ m ≤ 2000$) өгөгдөнө.

Дараагийн мөрөнд $m$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $i_{1}, i_{2}, ..., i_{m}$ ($1 ≤ i_{j} ≤ n$) өгөгдөх ба эдгээр нь өндөр тэмдэгт мөр $t$ дотор байх суурь тэмдэгт мөрүүдийн индексүүдийг илэрхийлнэ.

Сүүлийн мөрөнд хоосон биш тэмдэгт мөр $s$ өгөгдөнө. Тэмдэгт мөр $s$ нь Латин жижиг үсгүүдээс тогтсон байх бөгөөд уг тэмдэгт мөрийн урт нь $2000$ тэмдэгтээс хэтрэхгүй байна.

Гаралт

Өндөр тэмдэгт мөр $t$ болон тэмдэгт мөр $s$ доторх хамгийн урт ерөнхий дэд дарааллын (тэмдэгтүүдээс тогтох дараалал байна) уртыг хэвлэнэ үү. Хэрэв ямар ч ерөнхий дэд дараалал байхгүй бол 0 гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
cba
dgh
2
1 2
aedfhr
Гаралт
3
Оролт
2
b
a
5
1 2 1 2 1
aaa
Гаралт
2

Тэмдэглэл

$s$ тэмдэгт мөрийн урт гэдэг нь уг тэмдэгт мөр дотор байх тэмдэгтүүдийн тоог илэрхийлнэ. Хэрэв $s$ тэмдэгт мөрийн уртыг $|s|$ гэж тэмдэглэвэл $s$ тэмдэгт мөр нь $s = s_{1}s_{2}... s_{|s|}$ гэж дүрслэгдэх юм.

Хоосон биш тэмдэгт мөр $y = s[p_{1}p_{2}... p_{|y|}] = s_{p_{1}}s_{p_{2}}... s_{p_{|y|}}$ ($1 ≤ p_{1} < p_{2} < ... < p_{|y|} ≤ |s|$) нь $s$ тэмдэгт мөрийн дэд дараалал байх юм. Жишээлбэл "coders" гэдэг нь "codeforces" гэдгийн дэд дараалал болно.

Сэтгэгдлүүдийг ачааллаж байна...