Semi-decide Post's Correspondence Problem
Python 3, 223 216 199 192 191 189 183 bytes
Thanks to @KarlKastor for pointing out that I could use count
from itertools import*
j=''.join
def f(x):
 for l in count(1):
  for i in product(x,repeat=l):
   *b,=zip(*i);c=j(b[0])
   if c==j(b[1]):print(c,j(str(x.index(k)+1)for k in i));return

A function that takes input of a tuple of pairs of strings x in the form ((seq1,seq2),(seq1,seq2)...) and prints the output to STDOUT in the same format as the test cases.
To continuously output solutions rather than just one solution, remove the return statement.
How it works
The function generates all l-length arrangements of the string pairs using product, with l being initialised at 1. This list is then unpacked and transposed using zip; this leaves a two-element list, where the first element contains all the first strings in the pairs, and the second all the second strings in the pairs. Each element is concatenated to a string using join; if these are the same, we have a hit and the string is printed to STDOUT. The sequence of pair indices is then generated by looking up each pair in the original arrangement using index; these indices are concatenated to a string, and also printed to STDOUT. If no solution exists for that l, l is incremented and the process repeated.
Try it on Ideone