반복문 2개로 부분 문자열 구하기 C++ / Java / 파이썬

임의의 문자열이 있을 때 부분문자열을 구하려면 어떻게 해야 할까요?

예를들어 'abcd' 라는 문자열이 있다면 부분 문자열은

 

a

ab

abc

abcd

b

bc

bcd

c

cd

d

 

10개가 부분문자열입니다.

 

문자열의 인덱스를 0,1,2,3 이라고 생각해봅시다.

그리고 첫 인덱스, 마지막 인덱스를 반복문으로 찾는다고 생각해봅시다.

 

0 ~ 0 : a

0 ~ 1 : ab

0 ~ 2 : abc

0 ~ 3 : abcd

1 ~ 1 : b

1 ~ 2 : bc

1 ~ 3 : bcd

2 ~ 2 : c

2 ~ 3 : cd

3 ~ 3 : d

 

모양을 보니 for문을 2번 돌리고 첫 for문 i는 0부터 문자열 크기전까지 1씩 증가시키고,

두번째 for문은 j를 i로 선언해서 문자열 크기전까지 증가시키면 될 것 같습니다.

 

반복문 2개로 부분문자열을 모두 구할수 있습니다.

 

그렇다면 백준 11478번 서로 다른 부분 문자열의 개수 문제를 풀면서 확인해봅시다.

 

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

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

부분 문자열의 서로 다른 개수를 찾는 문제입니다.

부분 문자열을 구함과 동시에 중복되면 안됩니다.

그렇다면 중복을 허용하지 않고 O(1) 시간복잡도에 빠르게 원소를 찾을 수 있는 Map 또는 Set과 같은 자료구조를 활용하면 되겠습니다.

 

1. JAVA

각 언어별로 문자열을 자르는 함수명과 index 사용법이 조금씩 다릅니다.

그것에 따라 반복문의 i, j, 마지막 값을 적절히 조절하면 됩니다.

HashMap에 부분 문자열이 있는지 확인하면서 없는 경우만 넣습니다.

마지막에 크기를 출력하면 답입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {   
	public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
	    
        HashMap<String, Integer> a = new HashMap<String, Integer>();
	    
        for(int i = 0; i < S.length(); i++){
            for(int j = i+1; j <= S.length(); j++) {
                if(!a.containsKey(S.substring(i, j))) {
                    a.put(S.substring(i, j), 1);
                }
            }
        }
        System.out.println(a.size());
    }
}

2. C++

java와 조금 다른 부분을 확인해보시기 바랍니다.

Map 대신 Set을 사용하였습니다.

문자열을 자르는 함수는 첫 인자는 시작 인덱스, 두번째 인자는 문자열의 크기가 들어가는게 java와 다른점 입니다.

이러한 특성에 맞춰 반복문의 i, j를 조절하면 됩니다. 

#include <iostream>
#include <string>
#include <set>;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string S;
    cin >> S;

    set<string> a;

    for(int i = 0; i < S.size(); i++){
        for(int j = 1; j + i <= S.size(); j++) {
            a.insert(S.substr(i, j));
        }
    }
    cout << a.size() << '\n';
    return 0;
}

3. 파이썬

파이썬 소스는 매우 간단해서 설명을 생략합니다.

S = input()
a = set()
for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        a.add(S[i:j])
print(len(a))