# Check if strings are intersting

Two strings S and T are said to be interseting if there are two non-empty strings A and B such that S = A+B and T = B+A.How to find if two strings are intersting or not?

EXAMPLE : if S="tokyo" and T="kyoto", then the pair (S,T) is interesting, because we can find A="to" and B="kyo".

• By this, do you mean "design an algorithm to check if the condition holds"? How efficient do you need this algorithm to be? – Igor Rivin Jan 11 '14 at 17:25
• One idea: Compute hash for $T$ and $O(n)$ hash values for modified $S$. Examine cases where the hash values are equal. – user114628 Jan 11 '14 at 17:26
• @IgorRivin yeah...i want algorithm for this. (If possible a piece of code in c++ language).It should just do it in one read of both strings i think – user3001932 Jan 11 '14 at 17:27
• @user2943324 could u please explain it in context of above example? – user3001932 Jan 11 '14 at 17:29
• It was a bad idea, never mind. I think Igor's answer is the way to go. – user114628 Jan 11 '14 at 17:32

Search for $S$ in $T+T.$ That should be quick enough.