Adjacent Swaps

3.9

62 votes
Binary search algorithm, Medium, Hash function, Suffix array, Algorithms, String, Suffix array, Hashing algorithm
Problem

For a given two strings S and T, both of length N, the task is to answer Q queries.

Let Si be the ith letter of S, so S1 is the first letter of S. Moreover, let Si,j denote the substring of S starting with Si and ending in Sj. Ti,j is defined analogously. For example, if S=abba, then S2,4=bba. Each given query consists of 5 integers K,a,b,c,d. The answer to the query is YES if and only if substring Sa,b can be obtained from substring Tc,d by using at most K swaps adjacent letters of Tc,d. Otherwise the answer is NO. More formally, a single swap of adjacent letters in T is replacing simultaneously Ti with Tj and Tj with Ti for j=i+1, where 1i|T|1.

For example if S=abbab and T=ababa, then S1,3=abb can be obtained from T2,4=bab using a single swap. Moreover, if S=abcab and T=abcab, then S1,3=abc can be obtained from T3,5=cab using 2 swaps (first we can swap c with a and then c with b). Notice that this cannot be done using less than 2 swaps.

Input Format:

In the first line there is a single string S. In the second line there is a single string T. In the third line, there is a single integer Q denoting the number of queries to handle. Each of the following Q lines corresponds to a single query. In the ith of them, there are 5 space separated integers K,a,b,c,d describing the ith query.

Constraints:

1N105
1Q105
1abN
1cdN
0K2
each letter of S is either a, b or c

Output Format:

Output exactly Q lines. In the ith of them print YES if the answer to the ith query is positive. Otherwise, print NO.

Sample Input
babba
abbaa
3
1 2 3 3 4
1 2 4 2 4
2 2 4 2 4
Sample Output
YES
NO
YES
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the sample, for the input strings S=babba and T=abbaa, there are 4 queries to answer. In the first one, it is asked if S2,3=ab can be obtained from T3,4=ba using at most 1 swap. It can be achieved by performing the only available swap, so the answer is YES. In the second query, S2,4=abb, T2,4=bba and only one swap can be used. Since any single swap doesn’t produce the desired result, the answer for this query is NO. In the third query, given substring are the same as in the second query, but 2 swaps are allowed. The answer for this query is YES, because S2,4=abb can be obtained from T2,4=bba by first swapping b with a to get bab and then by swapping first b with a to get abb.

Editor Image

?