백준 5582번 공통 부분 문자열

문제 링크입니다: https://www.acmicpc.net/problem/5582

http://jaimemin.tistory.com/370과 유사한 문제였습니다.

LCS 문제 같은 경우 부분문자열이 연속하지 않아도 되지만 해당 문제는 연속하는 부분문자열이여야 했으므로 고려해야하는 부분이 추가되어 cache를 3차배열로 잡았습니다.

현재 이어나가는 부분문자열이 존재하는지 여부를 판별하기 위해 bool head를 선언하였고 나머지는 LCS 문제와 똑같이 탐색을 진행하면 됩니다.

#include <iostream>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

 

const int MAX = 4000;

 

string str1, str2;

int cache[2][MAX][MAX];

 

int longestSequence(bool head, int idx1, int idx2) //현재 이어지는 부분문자열 존재여부, str1 인덱스, str2 인덱스

{

        //기저 사례:문자열의 범위 벗어날 경우

        if (idx1 == str1.size() || idx2 == str2.size())

               return 0;

        int &result = cache[head][idx1][idx2];

        if (result != -1)

               return result;

 

        if (head == 0)

        {

               //부분문자열 시작점이 없으므로 탐색

               result = max(longestSequence(false, idx1 + 1, idx2), longestSequence(false, idx1, idx2 + 1));

               if(str1[idx1]==str2[idx2]) //같은 문자로 시작할 경우

                       result = max(result, 1 + longestSequence(true, idx1 + 1, idx2 + 1));

        }

        //현재 이어지는 문자열이 있을 경우

        else

        {

               if (str1[idx1] != str2[idx2]) //끊길 경우

                       result = 0;

               else //이어질 경우

                       result= 1 + longestSequence(true, idx1 + 1, idx2 + 1);

        }

        return result;

}

 

int main(void)

{

        cin >> str1 >> str2;

        memset(cache, -1, sizeof(cache));

        cout << longestSequence(0, 0, 0) << endl;

        return 0;

}