Submission #513722

#	Time	Username	Problem	Language	Result	Execution time	Memory
513722		Mahdi	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	1568 ms	208 KiB

necklace

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e5+5;
string s, t;
int n, m,ans, l, r;

void sol(){
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            int x=0;
            while(x<n-i && x<m-j && s[i+x]==t[j+x])
                ++x;
            int y=0;
            for(int k=min(n-i-x, j);k>=1;--k){
                bool bl=1;
                for(int o=1;o<=k;++o){
                    if(s[i+x+o-1]!=t[j-k+o-1]){
                        bl=0;
                        break;
                    }
                }
                if(bl){
                    y=k;
                    break;
                }
            }
            if(x+y>ans){
                ans=x+y;
                l=i;
                r=j-y;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>s>>t;
    n=s.size();
    m=t.size();
    ans=0;
    sol();
    int x=ans;
    reverse(all(t));
    sol();
    if(ans>x)
        r=m-r-ans;
    cout<<ans<<'\n'<<l<<' '<<r<<'\n';
}

• Subtask 1: 0 / 15