Charming
Пролетен Турнир по Информатика, 2010
Time Limit: 0.1s, 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" – в края му. Във втория виждаме, че не е задължително откритите последователности да са различни.
Мрън!