Using above approach, in the worst case scenario, you would need to compare the whole string in all queries, i.e., make N*Q = 10^9 comparisons. I think expected solution is closer to N^2 + Q = 2*10^6.
Consider for a moment a simpler problem, where in each query starting index for first and second string is the same, i.e., x_i = y_i. You should be able to solve this variant with O(N) precomputation and constant time for each query, i.e., O(N + Q) in total.
Now, observe that there are at most 2N different relative shifts in starting positions, i.e., possible values of x_i - y_i. If you apply the same solution to each of them, you have 2N*N precomputation time and constant time for each query, i.e., O(N^2 + Q) in total.