9526번 - 꿍글리쉬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 88 | 13 | 12 | 19.672% |
문제
꿍은 영타속도를 높이기 위해 열심히 노력했고 덕분에 순식간에 많은 영어를 입력할 수 있다.
하지만 영타속도만 높이다 보니 꿍이 입력하는 영어는 띄어쓰기와 문장부호가 전혀 없고 대소문자도 제멋대로인, 누구도 알아보기 힘든 '꿍글리쉬'가 되고 말았다. 예를 들어 영어로 "programming is great"과 같은 문장이 있다면 꿍은 "PrOgRAMmINgiSgrEAt"과 같이 꿍글리쉬로 만들어버린다.
꿍은 자신이 얼마나 복잡한 꿍글리쉬를 만들었는지 알아보기 위해 다음과 같은 과정을 진행하기로 했다. 먼저 꿍은 임의의 단어 T를 선택한다. 그 다음, 꿍글리쉬 문장의 부분 문자열에서 대소문자를 신경쓰지 않고 T를 모두 찾고, 각 경우마다 T와 대소문자가 몇 개가 다른지 계산한다. 이 값들 중 가장 큰 값이 꿍글리쉬의 복잡도를 나타낸다.
예를 들어, 꿍이 "GR"을 T로 선택하고 "PrOgRAMmINgiSgrEAt"에서 “PrOgRAM”을 부분 문자열로 선택했을 경우, T는 "gR"에서 한 번 나타나는데 이때 복잡도는 1이 된다. 같은 부분 문자열 "PrOgRAM"에서 "r"이 T로 선택된 경우 T는 "r"과 "R"에서 총 두 번 나타나는데 각각의 복잡도 후보는 0과 1이 되므로 이때의 복잡도는 1이 된다.
인성이 안 좋은 꿍은 여러분을 더욱 화나게 하기 위해 이 복잡도 계산을 더 힘들게 하고자 또 다른 규칙을 고안했다. 여러분은 한 번의 복잡도를 계산하고 나서는 선택된 부분 문자열의 대소문자를 바꾼 후 그 다음 복잡도를 계산할 수 있다. 예를 들어, "PrOgRAMmINgiSgrEAt"에서 "PrOgRAM"을 부분 문자열로 선택한 후 복잡도를 계산했다면 다음 복잡도를 계산하기 위해서는 "PrOgRAM"의 대소문자를 뒤집은 “pRoGrammINgiSgrEAt” 에 대해 복잡도를 계산해야 한다. 이어서 “pRoGrammINgiSgrEAt”의 부분 문자열 “ammINgi”에 대해 복잡도를 계산했다면 다음 복잡도를 계산하기 위해선 “pRoGrAMMinGISgrEAt”에 대해 복잡도를 계산해야 한다.
규칙을 만든 꿍 조차도 너무 헷갈린다. 그냥 여러분이 복잡도를 계산하는 프로그램을 만들자.
입력으로는 꿍이 선택한 T와 꿍글리쉬 문장 한 개, 그리고 꿍이 선택할 부분 문자열이 순서대로 주어질 것이며 여러분은 이 정보들을 이용하여 각 경우의 복잡도를 계산하면 된다.
입력
입력의 첫 번째 줄은 정수 N (1 ≤ N ≤ 105)과 최대 5글자인 T가 공백을 사이에 두고 주어지며 N은 부분 문자열의 선택 횟수를 나타낸다.
두 번째 줄은 공백이 없는 꿍글리쉬 문장 P가 주어지며 길이는 최대 100000이다.
다음 각 N줄은 두 개의 정수 L, R (1 ≤ L ≤ R ≤ |P|) 이 주어지며 꿍글리쉬 문장 P의 L~R번째의 부분 문자열의 복잡도를 계산함을 의미한다. 꿍글리쉬 문장의 가장 왼쪽 문자가 1번째 문자이며 가장 오론쪽 문자는 N번째 문자다.
출력
출력은 N줄로 이루어지며 각 줄은 하나의 정수를 포함한다.
각 줄에는 꿍글리쉬의 복잡도를 출력하며 만약 T가 꿍글리쉬 문장에 나타나지 않는 경우 -1을 출력한다.
예제 입력 1
3 gR PrOgRAMmINgiSgrEAt 1 7 4 18 6 14
예제 출력 1
0 2 -1
힌트
처음 꿍글리쉬 문장 : PrOgRAMmINgiSgrEAt
1~7번째 부분 문자열 : PrOgRAM (복잡도 후보 : 0)
바뀐 꿍글리쉬 문장 : pRoGrammINgiSgrEAt
4~18번째 부분 문자열 : GrammINgiSgrEAt (복잡도 후보 : 2,1)
바뀐 꿍글리쉬 문장 : pRogRAMMinGIsGReaT
6~14번째 부분 문자열 : AMMinGIsG (복잡도 후보 : 없음)
출처
ICPC > Regionals > Latin America > Latin America Regional Contests > Latin America Regional Contests 2013 B번
- 문제를 번역한 사람: seok9311
- 문제를 만든 사람: Fidel Schaposnik, Pablo Ariel Heiber, Rafael Garcia
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호