[Algospot] 알고스팟 작명하기(NAMING) 문제풀이(C++)

예전에 배웠던 KMP 알고리즘 다시 떠올릴 수 있는 문제였음

KMP 알고리즘 핵심 :

 1. 문자열 검색 도중 일치하는 부분이 나왔고, 그 다음문자가 불일치하면 -> 다음 비교위치는 [ 검색문자열에서 일치한 부분 ] 에서의  [ 최대길이 접두/접미사 ] 부분 이후부터라는 점

 2. 검색문자열 S에 대해 S[...i] 까지의 부분문자열의 최대 접두/접미사 길이를 pi[i]라 할 때, pi배열을 KMP개념을 이용하여 빠르게 구할 수 있음.

 

 

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
/*
<문제> - 500ms, 65536kb 제한
두 이름이 주어졌을 때, 두 이름을 합한 것에서
접두사도 되고 접미사도 되는 문자열들을 모두 찾기
 
<입력>
두 줄에 걸쳐 아버지, 어머니 이름 주어짐(합쳐서 40만 안넘음)
 
<출력>
접두/접미사가 되는 문자열들 길이를 오름차순으로 출력(공백하나 두고)
 
<풀이>
1. 아이디어 - KMP 이용 / pi[n]을 정의한 다음, 
   전체문자열 중에 검색하는 비교문자열 S에 대해 S[n]번째까지 동일한 경우에서, 
   다음 문자가 다르면 -> 이 문자의 다음 비교문자는 S[pi[n]]이 되는 것을 이용
  - pi배열 생성 - pi[n] : 기존 문자열의 부분문자열 S[...n] 중 가장 긴 접두/접미사의 길이 / 이거 생성 O(N+H)에 가능(이것도 KMP알고리즘 이용)
  - 검색문자위치와 비교문자위치 / 검색문자위치는 순차적으로 계속 증가할거고, 비교문자위치는 계속 변할거
  - 문자열 일치할 경우 : count++하며 계속 탐색
  - 문자열 불일치할 경우 : 비교문자열 S에 대해, S[pi[count]]부터 다시 탐색, count=pi[count]
 
2. 시간복잡도
  - O(M+N) / M은 총 문자열, N은 비교문자열
 
3. 변수
  - int now : 현재 비교위치
  - string name : 입력문자열
*/
 
int main() {
    
    string a, b; cin >> a >> b;
    string name = a + b;
    vector<int> pi(name.size(), 0);
    
    //pi배열 생성
    int now = 0;    //현재 비교위치
    for (int i = 1; i < name.size(); i++) { //i : 검색위치
            while (now > 0 && name[now] != name[i])  //now가 0이면 현재 비교대상이 처음문자이므로, name에서 다음 문자로 넘어감
                now = pi[now - 1];  // 현재 비교대상 : S[...now-1] 에서 최대길이 접두/접미사 다음위치
            if (name[now] == name[i]) pi[i] = ++now;  //현재 비교대상이 일치하면 p[i]값 수정한 후 다음 위치로 이동
    }
    //pi저장 완료
 
    now = name.size();  //현재 위치 - 처음엔 문자열 전체개수가 접두/접미사이기 때문에 이렇게 들어감
    vector<int> ans;
    while (now > 0) {
        ans.push_back(now);
        now = pi[now - 1];
    }
    
    for (int i = ans.size() - 1; i >= 0; i--) 
        cout << ans[i] << " ";
 
    return 0;
}