Monk and Match Making
Every query will have four integers - L1, R1, L2, R2. The first two integers denoting
String [ L1, R1 ] (including both L1 and R1) denoting the first substring, the next two integers denoting the second substring String [ L2, R2 ](including both L2 and R2).
For every query, you've to answer in Yes or No whether the two substrings are equal or not. Easy enough?
Input:
The first line contains a string, S.
Then, an integer Q denoting the number of queries in the next line.
Then, for every query, there will be 4 integers L1 R1 L2 R2, denoting the substring S[L1 R1] and S[L2 R2].
The first line contains a string, S.
Then, an integer Q denoting the number of queries in the next line.
Then, for every query, there will be 4 integers L1 R1 L2 R2, denoting the substring S[L1 R1] and S[L2 R2].
Output:
For each query output "Yes" if the two substrings are same , else output "No".
For each query output "Yes" if the two substrings are same , else output "No".
Constraints:
1 ≤ |S| ≤ 105
1 ≤ Q ≤ 105
1 ≤ L1 ≤ R1 ≤ |S|
1 ≤ L2 ≤ R2 ≤ |S|
The string will contain only lowercase letters.
1 ≤ |S| ≤ 105
1 ≤ Q ≤ 105
1 ≤ L1 ≤ R1 ≤ |S|
1 ≤ L2 ≤ R2 ≤ |S|
The string will contain only lowercase letters.
Sample Input
(Plaintext Link)monkandhismonkiness 4 1 1 3 3 1 4 11 14 3 3 6 6 4 5 14 17
Sample Output
(Plaintext Link)No Yes Yes No
Explanation
using namespace std;
typedef long long int lli;
//typedef long int li;
typedef unsigned long long int ulli;
#define ini(a, v) memset(a, v, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define test() int t; cin>>t;while(t--)
#define si(x) scanf("%d",&x)
#define slli(x) scanf("%lld",&x)
#define sli(x) scanf("%ld",&x)
#define sd(x) scanf("%d",&x)
#define pfi(x) printf("%d\n",x)
#define pfli(x) printf("%ld\n",x)
#define pflli(x) printf("%lld\n",x)
#define abs(x) ((x)>0?(x):-(x))
#define TRI(a,b,c) mp(mp(a,b),c)
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) // first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) // first element in the range [first,last) which compares greater than val.
#define all(x) x.begin(),x.end()
#define sz size()
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repl(i,a,b) for(lli i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define foreach( gg,itit ) for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
typedef pair<lli,lli> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
lli has1[1000010];
lli has2[1000010];
lli pow1[1000010];
lli pow2[1000010];
char s[1000010];
int main()
{
int t;
cin>>s+1;
cin>>t;
int p1=1000000007,p2=1000007;
int p3=100007,p4=1234567891;
int n=strlen(s+1);
pow1[0]=1;
pow2[0]=1;
for(int i=1;i<=n;i++)
{
pow1[i]=(pow1[i-1]*p1) %p2;
pow2[i]=(pow2[i-1]*p3) %p4;
}
for(int i=1;i<=n;i++)
{
has1[i]=(has1[i-1]*p1+s[i])%p2;
has2[i]=(has2[i-1]*p3+s[i]) %p4;
}
while(t--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b-a==d-c)
{
lli val1=(has1[b]-(pow1[b-a+1]*has1[a-1])%p2+p2)%p2;
lli val2=(has2[b]-(pow2[b-a+1]*has2[a-1])%p4+p4)%p4;
lli val3=(has1[d]-(pow1[d-c+1]*has1[c-1])%p2+p2)%p2;
lli val4=(has2[d]-(pow2[d-c+1]*has2[c-1])%p4+p4)%p4;
if(val1==val3 && val2==val4)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
else
cout<<"No"<<endl;
}
}
For Query 1 , it denotes the substrings "m" and "n" which do not match
For Query 2 , it denotes the substrings "monk" and "monk" which do match
For Query 3 , it denotes the substrings "n" and "n" which do match
For Query 4 , it denotes the substrings "ka" and "ki" which do not match
For Query 2 , it denotes the substrings "monk" and "monk" which do match
For Query 3 , it denotes the substrings "n" and "n" which do match
For Query 4 , it denotes the substrings "ka" and "ki" which do not match
----------------------------------------------------EDITORIAL---------------------------------------------------------------
Difficulty : Medium
Pre-Requisites : Hashing , Rolling Hash
Problem : Given a string S , many queries are given of the form L1 R1 L2 R2 which ask whether the substring S[L1...R1]and S[L2...R2] are same or not ?
Explanation :
The naive solution for this problem is to check in linear time whether the two given substrings are same or not which gives the time complexity of O(Q*N) which will lead to TLE.
The naive solution for this problem is to check in linear time whether the two given substrings are same or not which gives the time complexity of O(Q*N) which will lead to TLE.
What we can use to solve this problem is Hashing , that is if we have a way to get hash of any substring in O(1) time complexity then we can just compare the Hash of the two substrings whether they are equal or not . One type of hash function which we can use is of the from , for string S of length N the hash H(S) is given by , H(S[1...N]) = ( S[1] * BN-1 + ... + S[N-2] * B2 + S[N-1] * B+ S[N] ) % M
Now , if the Hash function is of the above type then we can see that for any random substring S[L...R] we can calculate its as , H(S[L...R]) = ( S[L] * BR-1 + ... + S[R-2] * B2 + S[R-1] * B+ S[R] ) % M
We can see that we can change the above equation into the following form ,
H(S[L...R]) = H(S[1...R]) - H(S[1...L-1]) * B(R-L+1)
Here , B and M and depends on the way you implement the Hash function.
Now , the problem with hashing is that a perfect hash function is not possible to be made so collisions can occur and it can give us a false match.
So , to solve this problem we can calculate two hashes for a substring using different B and M , and when matching two substrings both hashes of two substrings should be same . This reduces chance of a false match. Thus , we achieve the time complexity of O(N + Q).
Why some python solutions got accepted of worse complexity ?
Now you must have seen the setter solution and some python solutions also where they have simply sliced the substrings and compared them whether they are equal or not whereas same solution in other languages would lead to TLE .
This happens so because the way slicing is implemented and how strings are compared in python. What happens is that they are implemented very efficiently in Python using C . Instead of going further in to core code of Python the essential part is that strings in Python are compared using memcmp() function of C which compares memory blocks which works very fast due to compiler optimization. That is if people used memcmp in C , C++ they would also get accepted.
If you are interested in reading the backend code of Python for StringObject you can go read here :D
---------------------------------------------------------------CODE---------------------------------------------------------------
#include<bits/stdc++.h>using namespace std;
typedef long long int lli;
//typedef long int li;
typedef unsigned long long int ulli;
#define ini(a, v) memset(a, v, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define test() int t; cin>>t;while(t--)
#define si(x) scanf("%d",&x)
#define slli(x) scanf("%lld",&x)
#define sli(x) scanf("%ld",&x)
#define sd(x) scanf("%d",&x)
#define pfi(x) printf("%d\n",x)
#define pfli(x) printf("%ld\n",x)
#define pflli(x) printf("%lld\n",x)
#define abs(x) ((x)>0?(x):-(x))
#define TRI(a,b,c) mp(mp(a,b),c)
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) // first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) // first element in the range [first,last) which compares greater than val.
#define all(x) x.begin(),x.end()
#define sz size()
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repl(i,a,b) for(lli i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define foreach( gg,itit ) for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
typedef pair<lli,lli> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
lli has1[1000010];
lli has2[1000010];
lli pow1[1000010];
lli pow2[1000010];
char s[1000010];
int main()
{
int t;
cin>>s+1;
cin>>t;
int p1=1000000007,p2=1000007;
int p3=100007,p4=1234567891;
int n=strlen(s+1);
pow1[0]=1;
pow2[0]=1;
for(int i=1;i<=n;i++)
{
pow1[i]=(pow1[i-1]*p1) %p2;
pow2[i]=(pow2[i-1]*p3) %p4;
}
for(int i=1;i<=n;i++)
{
has1[i]=(has1[i-1]*p1+s[i])%p2;
has2[i]=(has2[i-1]*p3+s[i]) %p4;
}
while(t--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b-a==d-c)
{
lli val1=(has1[b]-(pow1[b-a+1]*has1[a-1])%p2+p2)%p2;
lli val2=(has2[b]-(pow2[b-a+1]*has2[a-1])%p4+p4)%p4;
lli val3=(has1[d]-(pow1[d-c+1]*has1[c-1])%p2+p2)%p2;
lli val4=(has2[d]-(pow2[d-c+1]*has2[c-1])%p4+p4)%p4;
if(val1==val3 && val2==val4)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
else
cout<<"No"<<endl;
}
}
