제출 #1010660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010660		ivopav	원형 문자열 (IZhO13_rowords)	C++17	20 / 100	2078 ms	6208 KiB

rowords

#include <bits/stdc++.h>
using namespace std;


int lcs(string a,string b,int n,int m){
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (a[i]==b[j]){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
        }
    }
    return dp[n][m];
}

int main(){
    string a;
    string b;
    cin >> a >> b;
    int n=a.size();
    int m=b.size();
    for (int i=0;i<n;i++){
        a.push_back(a[i]);
    }
    for (int i=0;i<m;i++){
        b.push_back(b[i]);
    }
    int najv=0;
    for (int i=0;i<n;i++){
        string c="";
        for (int j=i;j<i+n;j++){
            c+=a[j];
        }
        for (int j=0;j<m;j++){
            string d="";
            for (int k=j;k<j+m;k++){
                d+=b[k];
            }
            najv=max(najv,lcs(c,d,n,m));
        }
    }
    reverse(b.begin(),b.end());
    for (int i=0;i<n;i++){
        string c="";
        for (int j=i;j<i+n;j++){
            c+=a[j];
        }
        for (int j=0;j<m;j++){
            string d="";
            for (int k=j;k<j+m;k++){
                d+=b[k];
            }
            najv=max(najv,lcs(c,d,n,m));
        }
    }
    cout << najv << "\n";
    
}

• Subtask 1: 20 / 100