Search

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

태그
자료 구조
문자열
해시를 사용한 집합과 맵
트리를 사용한 집합과 맵

문제 설명

•
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 문제
◦
부분 문자열 = S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예제 입력/출력

•
입력1
ababc
Python
복사
•
출력1
12
Python
복사

제약 조건

•
1≤S≤1,0001 ≤ S ≤ 1,000
◦
SS는 알파벳 소문자로만 제한

문제 풀이

풀이1 모든 부분 문자열을 구하는 방법 - O(n(n+1)2×n)O(\frac{n(n+1)}{2} \times n)

풀이 코드

풀이1 모든 부분 문자열을 구하는 방법 - O(n(n+1)2×n)O(\frac{n(n+1)}{2} \times n)