2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ By this, do you mean "design an algorithm to check if the condition holds"? How efficient do you need this algorithm to be? $\endgroup$ – Igor Rivin Jan 11 '14 at 17:25
  • $\begingroup$ One idea: Compute hash for $T$ and $O(n)$ hash values for modified $S$. Examine cases where the hash values are equal. $\endgroup$ – user114628 Jan 11 '14 at 17:26
  • $\begingroup$ @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 $\endgroup$ – user3001932 Jan 11 '14 at 17:27
  • $\begingroup$ @user2943324 could u please explain it in context of above example? $\endgroup$ – user3001932 Jan 11 '14 at 17:29
  • $\begingroup$ It was a bad idea, never mind. I think Igor's answer is the way to go. $\endgroup$ – user114628 Jan 11 '14 at 17:32
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.