[BAEKJOON] 11478 서로 다른 부분 문자열의 개수

 

문제 이미지

서로 다른 부분 문자열의 개수

• 알고리즘 분류: 문자열 처리, 집합과 맵
• 난이도: Silver3
• 사이트 주소: 

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

11478번: 서로 다른 부분 문자열의 개수

문제 내용

• 입력된 문자열 S 1,000이하이다.
• 부분 문자열 길이 1부터 해서 입력된 문자열 길이까지 구한다.
• 그중 중복된것을 제외한 개수를 구하면 된다.

문제 풀이

• 집합 Set 자료구조를 선언한다.(중복된것 제거 가능하다.)
• 1부터 입력된 문자열 길이까지 각 경우의 문자 길이 잘라서 집합에 저장한다.

Python

S = input()
s = set({})
size = len(S)

for i in range(1, size + 1):
    for j in range(size - i + 1):
        s.add(S[j: j + i])

print(len(s))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException{

    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String S = br.readLine();
    	Set<String> set = new HashSet<>();
    	int size = S.length();
    	
    	for(int i = 1; i < size + 1; i++) {
    		for (int j = 0; j < size - i + 1; j++) {
    			set.add(S.substring(j,j+i));
    		}
    	}
     
    	System.out.println(set.size());
     }
     
}