[알고리즘] 실패 함수 - 중복 최대 부분문자열(cpp)

영어 소문자로 이루어진 최대 길이 1,000인 문자열에서, 두 번 이상 나오면서 가장 긴 부분문자열의 길이를 출력하는 프로그램을 작성하시오.
예를 들어, banana의 경우 길이가 5인 부분 문자열은 banan, anana, 길이가 4인 부분 문자열은 bana, anan, nana, 길이가 3인 부분 문자열은 ban, ana, nan, ana이므로 ana가 2번 나오면서 가장 길이가 길다. 답은 따라서 이 경우 3이 된다. 
힌트: 실패함수를 잘 이용해보자.

입력
표준 입력으로 입력을 받는다. 입력은 한 줄로 이루어지며, 최대 길이가 1,000인 영어 소문자로 이루어진 문자열이다. 

출력
표준 출력으로 출력한다. 출력은 한 줄로 이루어지며, 입력된 문자열에서 두번 이상 나오면서 가장 길이가 긴 부분 문자열의 길이를 출력한다. 

예제 입력 1
abcdefg
예제 출력 1
0

---

 

두 번 이상 나오면서 가장 긴 부분문자열의 길이를 구하는 과제!

한마디로 말하면 최대 패턴을 찾는 문제이다.

수업시간에 배운 실패함수를 사용하는 문제였다.

 

실패함수(failure function)

정의 : f(i)는 P[1..i]에서, 접두사=접미사이면서 가장 긴 것의 길이

• ➢  정의에 의해서, 0 ≤ f(i) < i (나중에 알고리즘 성능 분석에서 중요하게 쓰임)
• ➢  i+1번째 위치에서 매치가 실패하면, P[1..i]까지는 매치가 성공했다는 뜻
• ➢  앞 페이지 그림과 같이, 동일한 접두사와 접미사가 일치하게 만들면 다른 부분은 비교하지 않아도 된다. (추가로, 이 부분 다음부터만 비교하면 된다)
• ➢  i - f(i)만큼 P를 오른쪽으로 이동할 수 있다.

실패함수

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string banana;
    cin >> banana;

    int sameLen = banana.length() - 1;
    int searchLen = 2;
    bool escape = false;
    vector<int> sameLenList(banana.length() * banana.length());
    int listIndex = 0;

    while (!escape)
    {
        int start = 0;
        for (int k = 0; k < searchLen; ++k) {
            string search = "";
            for (int i = start; i < sameLen+start; ++i) {
                search = search + banana[i];
            }
            start++;
            string tmp = banana;
            
            if (banana.find(search) != string::npos)
            {
                tmp.erase(tmp.begin(), tmp.begin() + banana.find(search)+1);
                if (tmp.find(search) != string::npos)
                {
                    // cout << sameLen << "\n";
                    sameLenList[listIndex] = sameLen;
                    escape = true;
                    break;
                }
            }
            listIndex++;
        }
        sameLen--;
        searchLen++;
    }
    int result = *max_element(sameLenList.begin(), sameLenList.end());
    cout << result;
}