알고리즘 문제풀이/백준

백준 11478번- 서로 다른 부분 문자열의 개수

www.acmicpc.net/problem/11478

 

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

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

www.acmicpc.net

 

처음에 for문안에 find를 쓰니 시간초과가 되어 많이 고생했다. set이라는 자료형 이용하는것을 추천한다. 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
  string input;
  getline(cin,input);

  int length = input.size();
  string str;
  int n = length;
  set<string> s; 

  for(int j = 1; j<= length; j++){
    for(int i = 0; i<n; i++){
       str = input.substr(i,j);
       s.insert(str);
    }
    n = n - 1;
  }

  cout << s.size() << "\n";  
  
}