Charming
Пролетен Турнир по Информатика, 2010
Time Limit: 0.2s, Memory Limit: 64MiB
Ели е много чаровно момиче. И за разлика от повечето нейни приятелки, всяка от които има своя чар – усмивка, излъчване, хумор и т.н. Ели има много чарове. Ели е като стринг!
Учени от Българската Академия за Изследване на Генната Архитектура или накратко БАЗИНГА, са решили да изследват от какво произлизат всичките ѝ качества. За целта те са взели част от нейното ДНК и търсят познати последователности, съответстващи на различни качества. Помогнете им, като напишете програма, която по ДНК-то на Ели намира колко най-много (не задължително различни) непресичащи се познати последвателности могат да се намерят.
Учени от Българската Академия за Изследване на Генната Архитектура или накратко БАЗИНГА, са решили да изследват от какво произлизат всичките ѝ качества. За целта те са взели част от нейното ДНК и търсят познати последователности, съответстващи на различни качества. Помогнете им, като напишете програма, която по ДНК-то на Ели намира колко най-много (не задължително различни) непресичащи се познати последвателности могат да се намерят.
Вход
На първия ред на стандартния вход ще бъде зададено ДНК-то на Ели: стринг S, съставен от главните латински букви – 'G', 'A', 'T' и 'C'. На следващия ред ще бъде зададено цялото число N - броя познати последователности, с които учените разполагат. На последния ред ще бъдат зададени N стринга A1, A2, ..., AN от същите букви - познатите последователности.
Изход
Някакъв изход.
Ограничения
- 1 ≤ N ≤ 50
- 1 ≤ |Ai| ≤ 100
- 1 ≤ |S| ≤ 1,000
Примерен Вход | Примерен Изход |
---|---|
GATTACA 4 GAT ATTAC CACA ACA | 2 |
AAAAAAA 1 AA | 3 |
В първия пример можем да открием най-много две непресичащи се познати последователности – "GAT" в началото на ДНК-то и "ACA" – в края му. Във втория виждаме, че не е задължително откритите последователности да са различни.