Submission #888025

#	Time	Username	Problem	Language	Result	Execution time	Memory
888025		AltoTenor	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	7 ms	344 KiB

necklace

#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long


vector <ll> computeLookup(string s){
	ll n = s.size();
    vector <ll> ans (n,0);
    ll len = 0,i=1;
    while(i<n){
        if ( s[i] == s[len] ){
            len++;
            ans[i] = len;
            i++;
        }
        else if (len == 0){
            ans[i] = 0;
            i++;
        }
        else{
            len=ans[len-1];
        }
    }
    return ans;
}
    
bool isSubstr(string A,string B){
        //Code Here
        // cout<<A<<" " <<B<<endl;
        vector <ll> lps = computeLookup(B);
        ll j = 0, i = 0 , n = A.size() , m = B.size();
        while(n-i>=m-j){
            if ( A[i] == B[j] ){
                i++;
                j++;
            }
            if ( j == m ) {                                                     
                return true;
                j = lps[j-1];
            }
            else if (i<n && A[i]!=B[j]) {  
                if (j!=0){                                               
                    j = lps[j-1];                                               
                }                                                               
                else                                                            
                    i++;                                                        
            }                                                                   
        }
        return 0;
}

bool check(string a,string b){
    b+=b;
    if ( isSubstr(b , a) )
        return 1;
    reverse(a.begin(),a.end());
    return isSubstr(b,a);
}

void solve(){
    string s1,s2;
    cin>>s1>>s2;
    ll n = s1.length();
    ll m = s2.length();
    ll mn = min(m,n);
    for (ll k=mn;k>0;k--){
        for (ll i=0;i<n-k+1;i++){
            unordered_map<char,ll> mp1,mp2;
            for (ll j=i;j<i+k;j++){
                mp1[s1[j]]++;
            }
            for (ll j=0;j<k;j++){
                mp2[s2[j]]++;
            }
            if (mp1==mp2 && check(s1.substr(i,k),s2.substr(0,k))){
                cout<<k<<endl;
                cout<<i<<" "<<0<<endl;
                return;
            }
            for (ll j=k;j<m;j++){
                mp2[s2[j]]++;
                mp2[s2[j-k]]--;
                if (mp1 == mp2 && check(s1.substr(i,k),s2.substr(j-k,k)) ){
                    cout<<k<<endl;
                    cout<<i<<" "<<j-k<<endl;
                    return;
                }
            }

        }
    }
    return;

}


int main(){
    solve();
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40