문자열 판별

면접 대비

시간 제한2초메모리 제한512 MB

요약

길이 100 이하의 문자열 S와 100개 이하의 단어 목록이 주어질 때, 목록의 단어를 여러 번 사용해 S를 이어 붙여 만들 수 있는지 판별합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 문자열, 해시맵
정답자: 아직 제출이 없습니다

문제

알파벳 소문자로 이루어진 문자열 $S$ 와 단어 목록 $A$ 가 주어진다. $A$ 에 포함된 문자열을 한 개 이상 공백 없이 이어 붙여서 $S$ 를 만들 수 있는지 없는지 판별하는 프로그램을 작성하시오. $A$ 에 포함된 단어는 여러 번 사용할 수 있다.

입력

첫째 줄에 길이가 100 이하인 문자열 $S$ 가 주어진다. 둘째 줄에는 $A$ 에 포함된 문자열의 개수 $N$ ( $1 \le N \le 100$ )이 주어진다. 셋째 줄부터 $N$ 개의 줄에는 $A$ 에 포함된 단어가 한 줄에 하나씩 주어진다. $A$ 에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

$A$ 에 포함된 문자열로 $S$ 를 만들 수 있으면 1, 없으면 0을 출력한다.

예제1

예제 1
입력
```
softwarecontest
2
software
contest
```
예상 출력
```
1
```