1958번 LCS 3

https://www.acmicpc.net/problem/1958

3차원으로 확대되었다.

기본적인 구현 방식은 

일반적인 2개의 문자열에 대한 LCS와 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
int lcs[101][101][101] = { 0, };
 
string str1, str2, str3;
 
int main(void)
{
    string input1, input2, input3;
 
    cin >> input1 >> input2 >> input3;
 
    str1 = '0' + input1;
    str2 = '0' + input2;
    str3 = '0' + input3;
 
    int len1 = str1.length();
    int len2 = str2.length();
    int len3 = str3.length();
 
    for (int i = 0; i < str1.length(); i++)
        for (int j = 0; j < str2.length(); j++)
            for (int k = 0; k < str3.length(); k++)
            {
                if (i == 0 || j == 0 || k == 0)
                {
                    lcs[i][j][k] = 0;
                    continue;
                }
 
                if (str1.at(i) == str2.at(j) && str2.at(j) == str3.at(k) && str3.at(k) == str1.at(i))
                {
                    lcs[i][j][k] = lcs[i - 1][j - 1][k - 1] + 1;
                    continue;
                }
                else lcs[i][j][k] = max(lcs[i - 1][j][k], max(lcs[i][j - 1][k], lcs[i][j][k - 1]));
            }
    
    int i = len1 - 1;
    int j = len2 - 1;
    int k = len3 - 1;
 
    stack<int> st;
 
    while (lcs[i][j][k] != 0)
    {
        if (lcs[i][j][k] == lcs[i - 1][j][k]) --i;
        else if (lcs[i][j][k] == lcs[i][j - 1][k]) --j;
        else if (lcs[i][j][k] == lcs[i][j][k - 1]) --k;
        else if (lcs[i][j][k] == lcs[i - 1][j - 1][k - 1] + 1)
        {
            st.push(i);
 
            --i;
            --j;
            --k;
        }
    }
 
    printf("%d\n", lcs[len1 - 1][len2 - 1][len3 - 1]);
 
    /*
    // 단어 출력
    while (!st.empty())
    {
    cout << str1[st.top()];
    st.pop();
    }

    printf("\n");
    */
 
    return 0;
}