Submission #6580972


Source Code Expand

Copy
/*input
abcabab
ab
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb emplace_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define sz(_a) (ll)(_a.size())
#define FILL(n) memset(n,0,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
void computeLPSArray(string pat, int M, int* lps); 
int KMPSearch(string pat, string txt) 
{ 
    int M = (pat).length(); 
    int N = (txt).length(); 
  
    int lps[M]; 

    computeLPSArray(pat, M, lps); 
  
    int i = 0;
    int j = 0;
    set<int> s;
    while (i < N) { 
        if (pat[j] == txt[i]) { 
            j++; 
            i++; 
        } 
  
        if (j == M) { 
            s.insert(i-j);
            j = lps[j - 1]; 
        } 
        else if (i < N && pat[j] != txt[i]) { 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        } 
    } 
    int ans=0;
    for(auto x:s){
        int cnt=1;
        while(s.find(x+M)!=s.end()){
            cnt++;
            x=x+M;
            s.erase(s.find(x));
        }
        ans=max(ans,cnt);
    
    }
    return ans;
} 
void computeLPSArray(string pat, int M, int* lps) 
{ 
    int len = 0; 
  
    lps[0] = 0; 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else 
        { 
            if (len != 0) { 
                len = lps[len - 1]; 
            } 
            else 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
} 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string a,b;
    cin>>a>>b;
    
    while(a.length()<b.length()) a+=a;
a+=a;
    int x=a.length(),y=b.length();
    int z=KMPSearch(b,a);
    if(z==0){
        cout<<0;
    }
    else if(z>=(x/y)){
        cout<<-1;
    }
    else{
        cout<<z;
    }
}

Submission Info

Submission Time
Task F - Strings of Eternity
User zaneyu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2754 Byte
Status WA
Exec Time 1278 ms
Memory 80092 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 65
WA × 5
Set Name Test Cases
Sample a01, a02, a03
All a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56, b57, b58, b59, b60, b61, b62, b63, b64, b65, b66, b67, b68, b69, b70
Case Name Status Exec Time Memory
a01 AC 1 ms 256 KB
a02 AC 1 ms 256 KB
a03 AC 1 ms 256 KB
b04 AC 1 ms 256 KB
b05 AC 1 ms 256 KB
b06 AC 1 ms 256 KB
b07 AC 1 ms 256 KB
b08 AC 1 ms 256 KB
b09 AC 1 ms 256 KB
b10 AC 1 ms 256 KB
b11 AC 1 ms 256 KB
b12 AC 384 ms 28592 KB
b13 AC 1278 ms 80092 KB
b14 AC 371 ms 28592 KB
b15 AC 360 ms 30996 KB
b16 AC 615 ms 49072 KB
b17 AC 11 ms 5168 KB
b18 AC 11 ms 5168 KB
b19 AC 599 ms 49072 KB
b20 AC 11 ms 5168 KB
b21 AC 22 ms 7132 KB
b22 AC 13 ms 7132 KB
b23 AC 538 ms 42844 KB
b24 AC 239 ms 25648 KB
b25 WA 10 ms 5168 KB
b26 AC 150 ms 17840 KB
b27 AC 15 ms 7388 KB
b28 AC 294 ms 31452 KB
b29 AC 32 ms 10204 KB
b30 AC 33 ms 9820 KB
b31 AC 14 ms 7132 KB
b32 AC 10 ms 5168 KB
b33 WA 9 ms 5168 KB
b34 AC 9 ms 5168 KB
b35 AC 14 ms 7900 KB
b36 AC 8 ms 3632 KB
b37 AC 10 ms 5168 KB
b38 WA 9 ms 5168 KB
b39 AC 13 ms 7388 KB
b40 AC 9 ms 5168 KB
b41 WA 9 ms 5168 KB
b42 AC 13 ms 8028 KB
b43 AC 65 ms 13788 KB
b44 AC 9 ms 5168 KB
b45 AC 50 ms 12380 KB
b46 AC 14 ms 7132 KB
b47 AC 14 ms 6192 KB
b48 AC 11 ms 4400 KB
b49 AC 9 ms 5168 KB
b50 AC 9 ms 5168 KB
b51 AC 24 ms 9948 KB
b52 AC 9 ms 5168 KB
b53 AC 18 ms 8668 KB
b54 WA 9 ms 5168 KB
b55 AC 9 ms 5296 KB
b56 AC 7 ms 2480 KB
b57 AC 6 ms 2356 KB
b58 AC 3 ms 876 KB
b59 AC 1 ms 256 KB
b60 AC 3 ms 1212 KB
b61 AC 2 ms 512 KB
b62 AC 2 ms 896 KB
b63 AC 7 ms 2352 KB
b64 AC 10 ms 5168 KB
b65 AC 10 ms 5168 KB
b66 AC 13 ms 7772 KB
b67 AC 14 ms 7132 KB
b68 AC 9 ms 5168 KB
b69 AC 9 ms 5168 KB
b70 AC 14 ms 7132 KB