Q4 - 4 모든 아나그램 찾기

4. 모든 아나그램 찾기

 

* 설명

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

 

* 입력

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.

S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

 

* 출력

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

 

* 예시 입력 1 

bacaAacba

abc

* 예시 출력 1

3

 

* 힌트

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

 

import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String in1 = in.nextLine();
		String in2 = in.nextLine();
		
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for(char x : in2.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0)+1);
		}
		
		////슬라이딩창 만듬
		HashMap<Character, Integer> tmp = new HashMap<Character, Integer>();
		char[] charIn1 = in1.toCharArray();
		for(int i = 0; i< in2.length()-1; i++) {
			tmp.put(charIn1[i], tmp.getOrDefault(charIn1[i], 0)+1);
		}
		
		int lt = 0, count=0;
		for(int rt = in2.length()-1; rt< in1.length(); rt++) {
			tmp.put(charIn1[rt], tmp.getOrDefault(charIn1[rt], 0)+1);
			if(tmp.equals(map)) {
				count++;
			}
			tmp.put(charIn1[lt], tmp.get(charIn1[lt])-1);
			if(tmp.get(charIn1[lt]) == 0) {
				tmp.remove(charIn1[lt]);
			}
			lt++;
		}
		System.out.println(count);
		in.close();
		return;

	}

}

 

import java.util.*;
class Main {	
	public int solution(String a, String b){
		int answer=0;
		HashMap<Character, Integer> am=new HashMap<>();
		HashMap<Character, Integer> bm=new HashMap<>();
		for(char x : b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0)+1);
		int L=b.length()-1;
		for(int i=0; i<L; i++) am.put(a.charAt(i), am.getOrDefault(a.charAt(i), 0)+1);
		int lt=0;
		for(int rt=L; rt<a.length(); rt++){
			am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0)+1);
			if(am.equals(bm)) answer++;
			am.put(a.charAt(lt), am.get(a.charAt(lt))-1);
			if(am.get(a.charAt(lt))==0) am.remove(a.charAt(lt));
			lt++;
		}
		return answer;
	}
		

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String a=kb.next();
		String b=kb.next();
		System.out.print(T.solution(a, b));
	}
}