Given two coprime integers a and b and another integer n, is it possible that n=x*a+y*b for some non-negative integers x and y?
We assume a<b. All integers in the form of x*a+y*b can be partitioned into a goups G[i]={ x*a+y*b | (x*a+y*b)%a=i } for 0<=i<a. Furthermore, it's obvoisly G[i]={ lower[i], lower[i]+a, lower[i]+2*a,...}. If r=n%a, we only need to check whether n>=lower[r]. We have lower[r] = min{ y*b | y*b%a=r }  and it is can be calculated by the Euclid's algorithm.
Moreover, becauce (a-1)*b=max{ lower[i] | 0<=i<a }, so (a-1)*b-a is the maximum integer which is not in the form of x*a+y*b.

Given a string S, we are to find the longest sub-string s of S such that the reverse of s is exactly the same as s.
First insert a special character '#' between each pair of adjacent characters of S, in front of S and at the back of S. After that, we only need to check palindrome sub-strings of odd length.
Let P[i] be the largest integer d such that S[i-d,...,i+d] is a palindrome.  We calculate all P[i]s from left to right. When calculating P[i], we have to compare S[i+1] with S[i-1], S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same, otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons utilizing the previously calculated P[i]s. 
Assume P[a]+a=max{ P[j]+j :  j<i }. If P[a]+a >= i, then we have
P[i] >= min{ P[2*a-i],  2*a-i-(a- P[a])}.
Is it the algorithm linear time? The answer is yes.
First the overall number of unsuccessful comparisons is obviously at most N.
A more careful analysis show that S[i] would never be compared successfully with any S[j](j<i) after its first time successful comparison with some S[k] (k<i).
So the number of overall comparisons is a most 2N.