5683번 - 상학어 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 82 | 15 | 8 | 33.333% |
문제
이 세상에는 남규어와 재혁어가 있다. 그러나 언제부터인가 그 중간 단계인 상학어가 발생하였다.
상학어에 속하는 단어는 다음과 같이 만들어진다. 남규어에 속하는 단어 중 하나를 골라 길이 1 이상인 접두사를 하나 고른다. 재혁어에 속하는 단어 중 하나를 골라 길이 1 이상인 접미사를 하나 고른다. 둘을 남규어-재혁어 순으로 이어붙인다. 이렇게 하면 상학어 단어가 완성된다. 참 쉽죠? 예를 들면 남규어 단어 "abc"와 재혁어 단어 "de"가 있으면 "ae", "ade", "abe", "abde", "abce", "abcde" 등의 상학어 단어를 만들 수 있지만, "bce", "ace", "abc" 등은 만들 수 없다.
물론 단어를 막 만들다 보니 때로는 의미를 부여하기 힘들 수도 있지만 그런 건 아무래도 좋다. 남규어 사전과 재혁어 사전이 주어질 때, 중복되지 않는 상학어 단어가 최대 몇 개나 만들어질 수 있는지 구하는 프로그램을 작성하시오. 예를 들면 남규어 단어 "ab", "abc"와 재혁어 단어 "cd", "d"가 있다면 "abcd"는 2번 만들어지지만 중복되므로 한 번만 세야 한다.
입력
입력은 여러 개의 테스트 케이스로 주어져 있으며, "0 0"으로 끝난다. 각 테스트 케이스는 다음과 같은 형식으로 이루어져 있다.
첫째 줄에 남규어 단어의 개수 P, 재혁어 단어의 개수 S가 주어진다. (1 ≤ P, S ≤ 1000)
그 다음 P개의 줄에 남규어 단어가 각각 하나씩, 그 다음 S개의 줄에 재혁어 단어가 각각 하나씩 주어진다. 단어는 1글자 이상 1,000글자 이하의 영어 소문자로만 이루어져 있다. 한 언어 안에 중복되는 단어는 없으며, 한 언어 안에 속하는 단어의 글자 합은 최대 105글자다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 만들 수 있는 상학어 개수를 출력한다.
예제 입력 1
3 3 mais grande mundo mas grande mundo 1 5 a aaaaa aaaaaa aaaaaaa a aaaaaaaaa 1 1 abc abc 0 0
예제 출력 1
182 9 8
출처
ICPC > Regionals > Latin America > Latin America Regional Contests 2011 D번
- 문제를 번역한 사람: kks227
- 문제를 만든 사람: Pablo Ariel Heiber
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호