Codeforces Gym 100340I Longest Common Subpair 문자열 DP

제목 대의:
두 문자열 P와 Q를 제시하고 두 문자열 A와 B를 찾아내면 A, B는 모두 P의 무교집합 서브열이며 Q의 무교집합 문자열이기도 하다
A + B의 길이가 가장 긴 경우 A, B의 해를 묻는다
대략적인 사고방식:
dp[i][j]로 위 면 P의 i번째 문자를 끝으로 하고 아래 면 Q의 j번째 문자를 끝으로 하는 최대 길이를 나타내는 문자열 DP
그리고 f[i][j]는 P의 길이가 i의 접두사와 Q의 길이가 j의 접두사인 가장 긴 공통 문자열을 나타낸다. 따라서 f[i][j]는 dp[i][j]의 접두사와
그러면 문자열을 거꾸로 한 번 더 한 다음에 절단점을 일일이 들면 됩니다. 시간 복잡도 O(n*n)
메모리가 비교적 빡빡하기 때문에, 수조는 short를 열고 중복 사용해야 한다
코드는 다음과 같습니다.
Result  :  Accepted     Memory  :  53384 KB     Time  :  124 ms

/*
 * Author: Gatevin
 * Created Time:  2015/9/1 13:25:38
 * File Name: C.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;
#define SHOW_MEMORY(x) cout<<sizeof(x)/(1024.*1024.)<<"MB"<<endl
char s[3010];
char t[3010];
short dp[3010][3010];
short f[3010][3010];
short f2[3010][3010];
int len1, len2;

void find(int x, int y, int len)
{
    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= y; j++)
        {
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            if(dp[i][j] == len)
            {
                for(int k = i - len + 1; k <= i; k++)
                    printf("%c", s[k]);
                printf("
");
                return;
            }
        }
}

void find2(int x, int y, int len)
{
    for(int i = len1; i >= x; i--)
        for(int j = len2; j >= y; j--)
        {
            if(s[i] == t[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
            if(dp[i][j] == len)
            {
                for(int k = i; k <= i + len - 1; k++)
                    printf("%c", s[k]);
                printf("
");
                return;
            }
        }
}

int main()
{
    freopen("subpair.in", "r", stdin);
    freopen("subpair.out", "w", stdout);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    len1 = strlen(s + 1);
    len2 = strlen(t + 1);
    for(int i = 1; i <= len1; i++)
        for(int j = 1; j <= len2; j++)
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
    for(int i = 1; i <= len1; i++)
        for(int j = 1; j <= len2; j++)
        {
            f[i][j] = max(f[i][j - 1], f[i - 1][j]);
            f[i][j] = max(f[i][j], dp[i][j]);
        }
    for(int i = len1; i >= 1; i--)
        for(int j = len2; j >= 1; j--)
            if(s[i] == t[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
    for(int i = len1; i >= 1; i--)
        for(int j = len2; j >= 1; j--)
        {
            f2[i][j] = max(f2[i][j + 1], f2[i + 1][j]);
            f2[i][j] = max(f2[i][j], dp[i][j]);
        }
    int maxL = 0;
    int ansi = 0, ansj = 0, leni = 0, lenj = 0;
    for(int i = 0; i <= len1; i++)
        for(int j = 0; j <= len2; j++)
            if(maxL < f[i][j] + f2[i + 1][j + 1])
            {
                maxL = f[i][j] + f2[i + 1][j + 1];
                ansi = i, ansj = j;
                leni = f[i][j], lenj = f2[i + 1][j + 1];
            }
    if(f[ansi][ansj] == 0 && f2[ansi + 1][ansj + 1] == 0)
    {
        printf("

");
        return 0;
    }
    if(f[ansi][ansj] && f2[ansi + 1][ansj + 1] == 0)
    {
        find(ansi, ansj, leni);
        printf("
");
        return 0;
    }
    if(f[ansi][ansj] == 0 && f2[ansi + 1][ansj + 1])
    {
        printf("
");
        find2(ansi + 1, ansj + 1, lenj);
        return 0;
    }
    find(ansi, ansj, leni);
    find2(ansi + 1, ansj + 1, lenj);
    return 0;
}