Submission #6580972

---

Source Code Expand

/*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

Judge Result