백준 1701 Cubeditor

문제 링크 : https://www.acmicpc.net/problem/1701

※선행해야 할 알고리즘 : KMP Algorithm

Algorithm

부분 문자열마다의 pattern_table을 생성하여 그 중 값이 가장 큰 것을 return 한다.(해당 내용 : KMP Algorithm 참고)

1. 여기서 말하는 "부분 문자열" 마다의 의미는 예제 입력 "abcdabcabb"을 기준으로 다음과 같다.

 (1) abcdabcabb (부분 문자열 1)

 (2) bcdabcabb  (부분 문자열 2)

 (3) cdabcabb    (부분 문자열 3)

  .

  .

  .

 (10) b           (부분 문자열 10)

2. "pattern_table"의 의미는 다음과 같다.

문자열의 모든 부분 문자열의 접미사와 접두사가 같은 문자열의 문자 개수들을 나열한 table을 의미한다.

여기서, 접두사와 접미사는 말 그대로 문자열의 머리와 꼬리이다.

예를들어 "abcdabcaab"라는 문자가 있다면 접두사와 접미사는 다음과 같다.

접두사              접미사

  a b c d a b c a a b 

따라서, 해당 문자열의 PatternTable은 다음과 같다.

문자열              

a                        

ab                      

abc                     

abcd                  

abcda                

abcdab              

abcdabc            

abcdabca         

abcdabcaa        

abcdabcaab     

패턴 테이블

0 0 0 0 1 2 3 1 1 2 

3. 2번을 모든 부분 문자열에 반복하여 최대값을 return하는 소스코드는 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int maketable(string p) { int max = 0; vector<vector<int>> table; table.resize(p.size()); for (int k = 0; k < p.size(); k++) { table[k].resize(p.size()-k,0); string part = p.substr(k, p.size()); int j = 0; table[k][0] = 0; for (int i = 1; i < part.size(); i++) { while (j > 0 && part[i] != part[j]) j = table[k][j - 1]; if (part[i] == part[j]) table[k][i] = ++j; if (max < table[k][i]) max = table[k][i]; } } return max; } int main() { string p; getline(cin, p); printf("%d\n", maketable(p)); }