백준 1701번. Cubeditor(c++) / kmp

전형적인 kmp문제이다.

하지만 더 추가해야할 포인트가 있다.

 

입력받은 문자열에 대한 failure function을 작성해서 돌리되, 

kmp Algorithm은 맨 처음 문자부터 시작하기 때문에 접미사를 하나씩 지우면서 최대값을 찾아나갔다.

 

 

일단, kmp Algorithm에 대한 개념이 생소하신 분은 아래 링크를 참고해서 공부하시면 될 것 같습니다.

https://jason9319.tistory.com/130

KMP(Knuth–Morris–Pratt) 알고리즘

 

코드 첨부

// Cubeditor
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
string s, temp;
int final = 0;
 
vector<int> getPi(string p){//실패 함수 작성
    int m = (int)p.size(), j=0;
    vector<int> pi(m, 0);
    for(int i = 1; i< m ; i++){
        while(j > 0 && p[i] !=  p[j])
            j = pi[j-1];
        if(p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
 
int main()
{
    cin>>s;    
    temp = s;
 
    for (int i=0; i < s.size(); i++) {
        string temp = s.substr(i, s.size());
        auto matched = getPi(temp);
        
        for (int j=0; j <matched.size(); j++) {
            final = max(final, matched[j]);
        }
    }
 
    cout<<final<<"\n";
    return 0;
}

 

github 첨부

https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/1701.cpp

jungahshin/algorithm