11478. 서로 다른 부분 문자열의 개수 (자바, Java)

제한시간이 1초같아 촉박해보이지만, 문자열이 1000이하라 해볼만하다.

문자열 길이 1일때 n개, 2일때 n-1개, 3일떄 n-2개...n일때 1개 해서, 시간복잡도는 n(n+1)/2 이다.

따라서 n=1000을 넣어도 1초당 연산량인 10억개를 넘지 않아, 이중반복문을 써도 큰 제약이 없다.

 

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 str = br.readLine();
		Set <String> set = new HashSet<>();
		
		for (int i=0; i<str.length(); i++) {
			for (int j=i+1; j<=str.length();j++) {
				set.add(str.substring(i,j));
			}
		}
		
		System.out.println(set.size());
	}
}