[알고리즘] 모든 아나그램 찾기

[알고리즘] 모든 아나그램 찾기

설명

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

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

입력

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

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

출력

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

예시 입력 1 bacaAacba abc 예시 출력 1 3

힌트 출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다. 풀이 기분이 안좋았는데 1트에 풀어서 기분 좋아졌다 ^^

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class findAllAnagram { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int answer = 0; char[] sArr = st.nextToken().toCharArray(); st = new StringTokenizer(br.readLine()); char[] tArr = st.nextToken().toCharArray(); HashMap sMap = new HashMap<>(); HashMap tMap = new HashMap<>(); for(int i = 0; i < tArr.length; i++){ tMap.put(tArr[i], tMap.getOrDefault(tArr[i], 0) + 1); } for(int i = 0; i < tArr.length; i++){ sMap.put(sArr[i], sMap.getOrDefault(sArr[i], 0) + 1); } if (tMap.equals(sMap)) answer++; int lt = 0; for(int rt = tArr.length; rt < sArr.length; rt++){ sMap.put(sArr[rt], sMap.getOrDefault(sArr[rt], 0) + 1); sMap.put(sArr[lt], sMap.get(sArr[lt]) - 1); if(sMap.get(sArr[lt]) == 0) sMap.remove(sArr[lt]); if (tMap.equals(sMap)) answer++; lt++; } System.out.println(answer); } }

from http://til-blog.tistory.com/30 by ccl(A) rewrite - 2021-12-28 01:27:31