| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1342091 | zeyrugan | 원형 문자열 (IZhO13_rowords) | C++20 | 0 ms | 0 KiB |
\//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
(void)freopen("rowords.in","r",stdin);
(void)freopen("rowords.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));
}
string revB=B;
reverse(revB.begin(),revB.end());
string newRevB=revB+revB;
for(int i=0;i<m;i++){
string window=newRevB.substr(i,m);
lcslen=max(lcslen,lcs(A,window));
}
cout<<lcslen<<endl;
return 0;
}