OverlapFreeQ[a_String,b_String]:=If[StringLength[a]>StringLength[b],OFQ2[b,a],OFQ2[a,b]]
OFQ2[a_,b_]:=StringPosition[b,a,1]=={}&&MatchQ[StringPosition[a,Table[StringTake[b,-i],{i,StringLength[a]}],1],{}|{{x_,_}}/;x>1]&&MatchQ[StringPosition[b,Table[StringTake[a,-i],{i,StringLength[a]}],1],{}|{{x_,_}}/;x>1]
OverlapFreeQ[a_String]:=StringLength[a]==1||MatchQ[StringPosition[a,Table[StringTake[a,-i],{i,StringLength[a]-1}],1],{}|{{x_,_}}/;x>1]
Non-overlapping pairs of strings
Non-overlapping pairs of strings
With[{l=Table[FromCharacterCode[Rest[IntegerDigits[i,2]]+65],{i,2,63}]},Select[Join@@Outer[List,l,l],OverlapFreeQ@@#&&OverlapFreeQ[First[#]]&&OverlapFreeQ[Last[#]]&]]//Timing
{3.34Second,{{A,B},{B,A},{AABB,AABAB},{AABB,ABABB},{BBAA,BABAA},{BBAA,BBABA},{AAABB,AABAB},{AAABB,ABABB},{AABAB,AABB},{AABAB,AAABB},{AABAB,AABBB},{AABBB,AABAB},{AABBB,ABABB},{ABABB,AABB},{ABABB,AAABB},{ABABB,AABBB},{BABAA,BBAA},{BABAA,BBAAA},{BABAA,BBBAA},{BBAAA,BABAA},{BBAAA,BBABA},{BBABA,BBAA},{BBABA,BBAAA},{BBABA,BBBAA},{BBBAA,BABAA},{BBBAA,BBABA}}}
fnonover=Last[%];
fnonoverx=Drop[fnonover,2]
{{AABB,AABAB},{AABB,ABABB},{BBAA,BABAA},{BBAA,BBABA},{AAABB,AABAB},{AAABB,ABABB},{AABAB,AABB},{AABAB,AAABB},{AABAB,AABBB},{AABBB,AABAB},{AABBB,ABABB},{ABABB,AABB},{ABABB,AAABB},{ABABB,AABBB},{BABAA,BBAA},{BABAA,BBAAA},{BABAA,BBBAA},{BBAAA,BABAA},{BBAAA,BBABA},{BBABA,BBAA},{BBABA,BBAAA},{BBABA,BBBAA},{BBBAA,BABAA},{BBBAA,BBABA}}
Non-overlapping triples of strings
Non-overlapping triples of strings
With[{l=Table[FromCharacterCode[Rest[IntegerDigits[i,2]]+65],{i,2,15}]},Select[Flatten[Outer[List,l,l,l],2],And@@(OverlapFreeQ/@#)&&And@@(OverlapFreeQ[First[#],Last[#]]&/@NestList[RotateRight,#,2])&]]//Timing
{7.42Second,{}}
With[{l=Table[FromCharacterCode[Rest[IntegerDigits[i,2]]+65],{i,2,31}]},Select[Flatten[Outer[List,l,l,l],2],And@@(OverlapFreeQ/@#)&&And@@(OverlapFreeQ[First[#],Last[#]]&/@NestList[RotateRight,#,2])&]]//Timing
{51.03Second,{}}
With[{l=Table[FromCharacterCode[Rest[IntegerDigits[i,2]]+65],{i,2,63}]},Select[Flatten[Outer[List,l,l,l],2],And@@(OverlapFreeQ/@#)&&And@@(OverlapFreeQ[First[#],Last[#]]&/@NestList[RotateRight,#,2])&]]//Timing
{487.52Second,{}}
$Version
Linux 3.0 (October 4, 1996)
With[{l=Table[FromCharacterCode[Rest[IntegerDigits[i,2]]+65],{i,2,127}]},Select[Flatten[Outer[List,l,l,l],2],And@@(OverlapFreeQ/@#)&&And@@(OverlapFreeQ[First[#],Last[#]]&/@NestList[RotateRight,#,2])&]]//Timing
Length[Last[%6]]
216