#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<<i<<" "<<0<<endl;
cout<<k<<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<<i<<" "<<j-k<<endl;
cout<<k<<endl;
return;
}
}
}
}
return;
}
int main(){
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
