[2021 SCPC 2차 예선]

패턴 매칭

영어 소문자로 된 두 문자열 A와 B가 매치가 된다는 것은 다음과 같이 정의된다. 

    1. A와 B의 길이가 같다.

    2. A의 i번째와 j번째 글자가 같으면 B의 i번째와 j번째 글자도 같다. 

    3. A의 i번째와 j번째 글자가 다르면 B의 i번째와 j번째 글자도 다르다.

즉 문자열 abcd와 문자열 pqrs는 매치가 된다. 하지만, 문자열 abac와 문자열 pqrs는 매치가 되지 않는다. 



텍스트 T에 패턴 P가 등장한다는 것은 T에서 길이가 P와 같은 연속된 일부분이 위의 기준에 따라 P와 매치가 된다는 것으로 정의된다. T에서 P의 매치 횟수는 T에서 P가 등장하는 서로 다른 위치의 개수를 말한다.



텍스트 하나와 K개의 패턴을 입력으로 받아 각 패턴이 텍스트에 등장하는 횟수를 계산하는 프로그램을 작성하라.

• 제한시간: 전체 테스트 케이스는 24개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내) 
  
      제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
  
      그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
  
      그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
  
      이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
  
      C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
  
      제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
  
      만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
  
• 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
  
• 제출 제한 : 최대 10회

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,

이후 차례로  T 개의 테스트 케이스가 주어진다. (1 ≤ T ≤ 24) 

각 테스트 케이스의 첫 줄에는 텍스트의 길이 N과 패턴의 개수 K가 주어진다. (1≤N≤2,000,000).

패턴의 최대 길이는 N과 500 중 작은 값이다. 한 케이스에서 패턴 길이의 총 합은 30,000을 넘지 않는다.

다음 줄에 텍스트가 영어 소문자의 문자열로 주어진다.

다음 K 줄에 각각 하나의 패턴이 영어 소문자의 문자열로 주어진다. 

• 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 400 점)
  
     주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
  
   각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
  
  
  
  ㆍ 그룹 1 (81 점) : 이 그룹의 테스트 케이스에서는 N≤3,000, 패턴의 길이는 최대 20, N⋅K≤10,000,000이다.
  
  ㆍ 그룹 2 (128 점) : 이 그룹의 테스트 케이스에서는 N⋅K≤10,000,000이다.
  
  ㆍ 그룹 3 (191 점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
  
  
  

• 모든 그룹을 해결하지 않는 소스코드를 제출하는 경우에도 모든 입력 케이스에 대해 양식을 갖춘 출력을 생성해야 합니다.

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

그 다음 줄에, (첫번째 패턴의 매치 횟수)×1, (두번째 패턴의 매치 횟수) ×2, …, (K번째 패턴의 매치 횟수) ×K를 모두 더한 값을 출력한다.

입출력예

입력
3 9 1 dabacadab nxyxz 20 2 abracadabracadabraaa abracadabra aa 18 2 abracadabracadabra abracadabra a

출력
Case #1 3 Case #2 6 Case #3 38

돌아가기