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

 

 

저번 문제인 18870에서 썻던것과 비슷한 방법으로 풀어봤다.

https://siko12.tistory.com/10

백준 18870 실패

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main()

{

    cin.sync_with_stdio(false);

    cin.tie(NULL);

    string s;

    vector<string> c;

    c.reserve(1000);

    cin >> s;

    //잘라낼 길이 1~ 전체까지

    for (int i = 1; i <= s.size(); i++)

    {

        for (int j = 0; j+i-1 < s.size() ; j++)

        {

            string ss;//잘라낸 스트링

            ss = s.substr(j,i);

            c.emplace_back(ss);

        }

    }

    sort(c.begin(),c.end());

    c.erase(unique(c.begin(),c.end()),c.end());

   

    cout << c.size();

}

/* 결과 성공했지만 삽입시 중복검사와 정렬을 함께한는 set이 더빠름 나는 한번에 하는편이 빠를줄 알았지...*/

그런데 0ms만에 푸는 방법이 있어 살펴 보았는데 아직 잘 모르겠다.

 

추가

harinboy님의 풀이를 보고 접미사 배열이라는것을 볼 수 있었고

관련된 것을 찾다 보 문자열 알고리즘에 대해 더 공부해보는것도 좋을것 같다는 생각도 든다.

https://blog.myungwoo.kr/57

Suffix Array와 LCP

 

 

https://namu.wiki/w/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문자열 알고리즘 - 나무위키