백준 1593

문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.

마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.

마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.

고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.

W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

풀이

S 문자열 안에서 처음부터 돌면서 W의 원소가 전부 있는지를 판단하면 풀린다.

단순하게 이중포문으로 비교하게 된다면 최소연산의 개수가 |S| * |W| 개 이므로 1초 훨씬 넘게 걸리게 된다.

그러므로 l = 0, r = W.size()-1로 표현해 r이 W.size()가 될때까지 하나씩 늘려가면서 확인하면 |S| * 57('A' ~ 'z' 아스키 코드 개수)가 걸려 쉽게 문제를 풀 수 있게 된다.

 

 

코드

#include <iostream>
#include <string>
using namespace std;
int g, s, ans[58], check[58], ans_num;
string W, S;
int main() {
    cin>>g>>s>>W>>S;
    for(int i=0; i<W.size(); i++) {
        ans[W[i]-'A'] += 1;
    }
    int l = 0, r = W.size()-1;
    for(int i=l; i<=r; i++)
        check[S[i]-'A'] += 1;
    while(r<S.size()) {
        int check_ans = 1;
        for(int i=0; i<58; i++) {
            if(ans[i] != check[i]) check_ans = 0;
        }
        if(check_ans) ans_num += 1;
        check[S[l]-'A'] -= 1;
        l += 1; r += 1;
        if(r == S.size()) break;
        check[S[r]-'A'] += 1;
    }
    cout<<ans_num;
}