제출 #205081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205081		moonrabbit2	원형 문자열 (IZhO13_rowords)	C++17	100 / 100	138 ms	126364 KiB

rowords

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
const ll mod=998244353,inf=1e18;
const int N=2005,M=1e6+5,K=1e5+5;
string s,t;
int n,m,k,V[N][2*N],H[N][2*N],ans[N][2*N],D[N][2*N],A[2*N],res;
void solve(){
    memset(V,0,sizeof(V));
    memset(H,0,sizeof(H));
    memset(ans,0,sizeof(ans));
    memset(D,0,sizeof(D));
    memset(A,0,sizeof(A));
    for(int i=1;i<=m;i++) H[0][i]=i;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        if(s[i]==t[j]){
            H[i][j]=V[i][j-1];
            V[i][j]=H[i-1][j];
        } else{
            H[i][j]=max(V[i][j-1],H[i-1][j]);
            V[i][j]=min(V[i][j-1],H[i-1][j]);
        }
    }
    D[0][0]=1;
    for(int i=1;i<=m;i++){
        assert(H[n][i]<=i);
        if(H[n][i]==0) D[0][i]=1;
        else A[H[n][i]]=i;
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++) if(i-1!=j) D[i][j]=D[i-1][j];
        D[i][A[i]]=1;
    }
    for(int i=0;i<k;i++) 
        for(int j=i+1;j<=m;j++) ans[i][j]=ans[i][j-1]+D[i][j];
    for(int i=1;i<=k;i++) res=max(res,ans[i-1][i+k-1]);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
    cin>>s>>t;
    n=s.size(); k=t.size(); m=2*k; s=" "+s; t=" "+t+t;
    solve();
    reverse(t.begin()+1,t.begin()+1+m);
    solve();
    cout<<res;
    return 0;
}

• Subtask 1: 100 / 100