시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 137 | 33 | 26 | 41.935% |
상근이는 긴 단어를 작은 단어로 나누려고 한다. 이때, 작은 단어는 모두 입력으로 주어지는 집합 S에 포함되는 단어이어야 한다.
단어를 나누는 방법의 수를 구하는 프로그램을 작성하시오.
경우의 수가 매우 커질 수 있기 때문에 1337377로 나눈 나머지를 출력한다.
첫째 줄에 긴 단어가 주어진다. 이 단어는 최대 300,000글자로 이루어져 있다.
둘째 줄에는 집합 S에 포함되어 있는 집합의 개수 N이 주어진다. (1 ≤ N ≤ 4,000)
다음 N개 줄에는 집합에 포함되어 있는 단어가 한 줄에 하나씩 주어진다. 단어는 최대 100글자로 이루어져 있고, 알파벳 소문자로만 이루어져 있다. 두 단어가 서로 같은 경우는 없다.
첫째 줄에 문제의 설명에 나와있는 것 처럼 긴 단어를 작은 단어로 나누는 경우의 수를 출력한다.
abcd 4 a b cd ab
2
afrikapaprika 4 afr ika pap r
1
ababababababababababababababababababababab 3 a b ab
759775
Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Final Exam #1 2번