문제
석표는 평소에 문자열을 가지고 노는 것을 좋아한다. 다음 조건을 만족하는 두 문자열은 닮았다고 한다.
1. 두 문자열이 같은 길이를 가지고 있다.
2. 길이 내의 모든 정수쌍 (i, j) 에 있어서, a[i]==a[j]이면 b[i]==b[j]이고, a[i]!=a[j]이면, b[i]!=b[j]이다.
예를 들어, a = ”adba”와 b = ”bcgb”는 닮았다. i=0이고, j=3이면, a[0] == a[3]이고 b[0]==b[3]이다.
다른 (i, j)쌍을 고르면, a에서도 b에서도 서로 다르다.
석표는 문자열 S를 가지고 있다. 심심했던 석표는 S의 부분문자열[l, r]과 닮은 부분문자열이 총 몇 개 있나 알아보고 싶다.
부분문자열[l, r]이란, S의 l번 인덱스부터 r번 인덱스까지의 연속된 문자열이다.
각 q개의 l과 r에 있어서, 부분문자열[l, r]과 닮은 S의 부분문자열의 수를 모두 출력하는 프로그램을 작성하라.
입력
표준 입력으로 다음 정보가 들어온다.
첫 줄에 n과 q가 공백을 사이에 두고 입력된다. n은 문자열 S의 길이이고, q는 석표가 알아보고 싶은 l, r 질문의 수이다.
둘째 줄에 문자열 S가 입력된다.
다음 q개의 줄에, l과 r 이 공백을 사이에 두고 입력된다.
(1 <= n, q <= 50,000, 1 <= l <= r <= n, S를 구성하는 문자는 소문자 알파벳 ‘a’부터 ‘j’까지뿐이다)
출력
표준 출력으로 다음을 출력한다.
q줄에 걸쳐, 각 질문별로 부분문자열[l, r]과 닮은 부분문자열의 수를 모두 출력한다.
<부분문제의 제약 조건>
부분문제 1: 전체 점수 100점 중 25점에 해당하며, 1 <= n, q <= 300이다.
부분문제 2: 전체 점수 100점 중 25점에 해당하며, 1 <= n, q <= 5,000이다.
부분문제 3: 전체 점수 100점 중 50점에 해당하며, 주어진 조건 외에 아무런 제약이 없다.
예제
8 4
giggabaj
1 1
1 2
1 3
2 4
8
6
2
1
출처
Hackerrank, string problems.
로그인해야 코드를 작성할 수 있어요.