Python 413

Pretty efficient, although it does sacrifice a small amount of speed for length, such as calculating things every pass of a small for loop rather than precalculating it. I̶t̶ ̶s̶t̶i̶l̶l̶ ̶o̶u̶t̶p̶u̶t̶s̶ ̶a̶l̶l̶ ̶t̶h̶e̶ ̶t̶e̶s̶t̶ ̶c̶a̶s̶e̶s̶ ̶i̶n̶ ̶w̶e̶l̶l̶ ̶u̶n̶d̶e̶r̶ ̶a̶ ̶s̶e̶c̶o̶n̶d̶.̶

Edit: I had to fix a bug which now makes it significantly less efficient for larger inputs.

X,Y,L=input();S=sorted;T=type def E(s,c): l=[[]] for h in s: if h==c:l+=[h] elif all(h!=[b,a][j]for a,b in L for j,n in[(0,a),(1,b)]if n==c): if T(l[-1])==str:l+=[[]] l[-1]=S(l[-1]+[h]) if T(l[0])==T(l[-1])!=str:return[l[0]+l[-1]]+l[1:-1]+[len(l[-1])] return l+[0] print any(0==cmp(*[[E(s,c)for c in S(set(s))]for s in [X[j:]+X[:j],Y[i:]+Y[:i]]])for i in range(len(Y))for j in range(len(X))) 

Test Cases

"acb", "abc", [('a','b')] True (0 ms) 'acabd','dcaba',[('a','b'),('a','c')] True (1 ms) 'acabd','acdab',[('a','b'),('a','c')] False (2 ms) 'cdaddccabbdcddcababaaabbcbdccaccacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')] True (62 ms) 'cdaddccabbdcddcababaaabbcbdcccacacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')] False (6963 ms) 

The basic algorithm does the following. For each letter, L, present, loop through the string constructing a list; anytime it encounters L it appends it to the list, any group of adjacent letters which can not be switched with L it appends to the list sorted, letters which can be switched with L are ignored.

For example when considering 'acabd' with the pairs [('a','b'),('a','c')], we would construct:

a : a, a, [d] b : [c], b, [d] * c : c, [b,d] d : [a,a,b,c], d 

which is equivalent to the result we get when we apply this to 'cabad' ('dcaba' shifted)

*Note here that the [c] and [d] should be considered one list

What is basically being done, is confirming for each letter that the order of it and the letters it can't switch with are the same. Since they cannot switch, they cannot 'pass' each other, so if the first string has two as followed by two ds followed by one a followed by one d than no matter how it's manipulated it can't be transformed into a string which has three as followed by three ds. Of course the order of the letters that it can't switch with is not an issue (they might be paired with each other and switchable), but their counts are, hence the sorting of the lists before comparison. In addition it's clear that any letters that can be switched don't matter at all for the purposed of comparison.

Using this algorithm the program could be made significantly more efficient; currently it loops through every possible transposition of both strings and compares them due to some issues with comparing cases in which there were lists bordering the beginning and end.

Haskell, 409

not fully golfed yet.

import Data.List r((c,h):s)|l<-r s,(x,y)<-partition(\s->any(`elem`s)[c,h])l=nub(c:h:concat x):y r _=[] k s d|l<-sort$nub s=r[(x,y)|x<-l,y<-l,notElem(x,y)d,notElem(y,x)d,x/=y] m a b c|elem c[a,b]=c|0<1=' ' e s d=[nub[map(m x y)s|x<-g,y<-g,notElem(x,y)d,notElem(y,x)d,x/=y]|g<-k s d] q a b=and$zipWith(\a b->or[n a==n[drop i s++take i s|s<-b]|i<-[0..length$a!!0]])a b f a b d=q(e a d)(e b d) n=map$filter(/=' ') 

this works on all the test cases.