Suppose we are give two strings 'x' and 'y' of same length p (1 <= p <= 200000). Each string consists of atmost 3 distinct characters. These 3 distinct characters are same in both string. I want to find number of indices j such that x[j]=y[j] between a suffix of string 'x' of length l and prefix of string 'y' of same length l. I want to print answer for each l (1<=l<=p). For example: x : "dfgd" and Y : "gfdf". Answer for suffix of length 3 of string x and prefix of length 3 of string y is 1.I have to print answer for each l (1<=l<=p). Any suggestions?

Suppose we are given an Array A of size N (N<=100000) and each element of array A[i]<=100000. Now I want to find index of rightmost element 'j' in subarray A[1]....A[i-1] for each A[i] such that gcd(A[j],A[i]) is 1 i.e. both are relatively comprime. How can this be done efficiently?