Submission #1342090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342090		zeyrugan	Round words (IZhO13_rowords)	C++20	0 / 100	1 ms	344 KiB

rowords

//ROUND WORD
// so here we can merge b as B=B+B then any rotation of B is from B+B and then we can use LCS
//https://oj.uz/problem/view/IZhO13_rowords

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

int lcs(const string &a,const string& window){
    int n=a.length();
    int m=window.length();

    vector<int> prev(m+1,0),curr(m+1,0);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i-1]==window[j-1]){
                curr[j]=prev[j-1]+1;
            }
            else{
                curr[j]=max(prev[j],curr[j-1]);
            }
        }
        swap(prev,curr);
    }
    return prev[m];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    #ifndef ONLINE_JUDGE
    freopen("rowards.in","r",stdin);
    freopen("rowards.out","w",stdout);
    #endif
    
    string A,B;
    cin>>A>>B;

    if(B.length()>A.length()){
        swap(A,B);
    }

    string newB=B+B;
    
    int m=B.size();
    int lcslen=0;
    for(int i=0;i<m;i++){
        string window=newB.substr(i,m);
        lcslen=max(lcslen,lcs(A,window));
    }
    cout<<lcslen<<endl;
    return 0;
}

Compilation message (stderr)

rowords.cpp: In function 'int main()':
rowords.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen("rowards.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("rowards.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100