백준 1593 : 문자 해독

https://www.acmicpc.net/problem/1593

1593번: 문자 해독

[ 문제풀이 ]

W의 길이가 최대 3000이기 때문에 W의 문자들로 만들 수 있는 모든 순열을 생성 후 검사한다면 시간초과가 발생하게 된다.검사해야하는 문자열의 길이는 고정이기 때문에 슬라이딩 윈도우 기법을 사용하여 구간을 검사해나가면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
     
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));) 
        {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int g = Integer.parseInt(st.nextToken());
        	int s = Integer.parseInt(st.nextToken());
            String W = br.readLine();
            String S = br.readLine();
            
            int[] cnt = new int[123];
            int[] temp = new int[123];
            for (int i = 0; i < g; ++i) {
            	cnt[(int)W.charAt(i)]++;
            }

            /**
             * (l~l+g) 슬라이딩 윈도우
             * if fail then if 존재하지 않는 문자 then l~t-1 구간 문자 제거
             *              else W의 문자보다 많음 then l~t-1구간에서 현재 문자가 나올때까지 제거
             * else 문자 개수 증가
             * success => l++
             */
            int l = 0, t = 0, answer = 0;
            while (l <= s - g) {
            	boolean flag = true;
            	for (; t < l + g; ++t) {
            		int idx = (int)S.charAt(t);
            		if (cnt[idx] == 0) {
            			for (int i = l; i < t; ++i) {
            				int idx2 = (int) S.charAt(i);
            				temp[idx2]--;
            			}
            			l = ++t;
            			flag = false;
            			break;
            		} else if (temp[idx] == cnt[idx]) {
            			for (int i = l; i < t; ++i) {
            				int idx2 = (int) S.charAt(i);
            				temp[idx2]--;
            				if (S.charAt(i) == S.charAt(t)) {
            					l = i + 1;
            					break;
            				}
            			}
            			flag = false;
            			break;
            		} else {
            			temp[idx]++;
            		}
            	}
            	if (flag) {
            		answer++;
            		temp[(int)S.charAt(l)]--;
            		l++;
            	}
            }
            bw.write(answer + "\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}