제출 #1010668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010668		ivopav	원형 문자열 (IZhO13_rowords)	C++17	20 / 100	2098 ms	6036 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;
    if (a.size()*b.size()>-7000){
        vector<int> kola(26,0);
        vector<int> kolb(26,0);
        for (int i=0;i<a.size();i++){
            kola[a[i]-'a']++;
        }
        for (int i=0;i<b.size();i++){
            kolb[b[i]-'a']++;
        }
        int rje=0;
        for (int i=0;i<26;i++){
            rje+=min(kola[i],kolb[i]);
        }
        cout << rje << "\n";
        
        exit(0);
    }
    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";
    
}

컴파일 시 표준 에러 (stderr) 메시지

rowords.cpp: In function 'int main()':
rowords.cpp:24:26: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if (a.size()*b.size()>-7000){
      |         ~~~~~~~~~~~~~~~~~^~~~~~
rowords.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i=0;i<a.size();i++){
      |                      ~^~~~~~~~~
rowords.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i=0;i<b.size();i++){
      |                      ~^~~~~~~~~

• Subtask 1: 20 / 100