Problem:
Problem B: Repeated Substitution with Sed Do you know "sed," a tool provided with Unix? Its most popular use is to substitute every
occurrence of a string contained in the input string (actually each input line) with another
string β . More precisely, it proceeds as follows.  Within the input string, every non-overlapping (but possibly adjacent) occurrences of α are
      marked. If there is more than one possibility for non-overlapping matching, the leftmost
      one is chosen.  Each of the marked occurrences is substituted with β to obtain the output string; other
      parts of the input string remain intact.  For example, when α is " aa " and β is " bca ", an input string " aaxaaa " will produce " bcaxbcaa ",
but not " aaxbcaa " nor " bcaxabca ". Further application of the same substitution to the string
" bcaxbcaa " will result in " bcaxbcbca ", but this is another substitution, which is counted as the
second one. In this problem, a set of substitution pairs ( α i , β i ) ( i = 1, 2, ... , n ), an initial string γ , and a
final string δ are given, and you must investigate how to produce δ from γ with a minimum
number of substitutions. A single substitution ( α i , β i ) here means simultaneously substituting
all the non-overlapping occurrences of α i , in the sense described above, with β i . You may use a specific substitution ( α i , β i ) multiple times, including zero times. Input The input consists of multiple datasets, each in the following format.  n  α 1  β 1  α 2  β 2 . . .  α n  β n  γ  δ   n is a positive integer indicating the number of pairs. α i and β i are separated by a single space.
You may assume that 1 ≤ | α i | < | β i | ≤ 10 for any i (| s | means the length of the string s ), α i ≠ α j for any i ≠ j , n ≤ 10 and 1 ≤ | γ | < | δ | ≤ 10. All the strings consist solely of lowercase
letters. The end of the input is indicated by a line containing a single zero. Output For each dataset, output the minimum number of substitutions to obtain δ from γ . If δ cannot
be produced from γ with the given set of substitutions, output -1 . Sample Input 2
a bb
b aa
a
bbbbbbbb
1
a aa
a
aaaaa
3
ab aab
abc aadc
ad dee
abc
deeeeeeeec
10
a abc
b bai
c acf
d bed
e abh
f fag
g abe
h bag
i aaj
j bbb
a
abacfaabe
0 Output for the Sample Input 3
-1
7
4

Solution (Python):
while 1:
    n = int(raw_input())
    if n == 0: break
    ab = [raw_input().split() for i in xrange(n)]
    s = raw_input()
    g = raw_input()
    memo = set([s])
    que = [[s,0]]
    while que:
        c,i = que.pop(0)
        if c == g:
            print i
            break
        for a,b in ab:
            cc = c.replace(a,b)
            if len(cc) > len(g) or cc in memo: continue
            memo.add(cc)
            que.append([cc,i+1])
    else:
        print -1

Solution (Python):
INF = 10**9
def dfs(s, d, P):
    if len(s) > len(d):
        return INF
    if s == d:
        return 0
    if s in memo:
        return memo[s]
    res = INF
    for a, b in P:
        r = s.replace(a, b)
        if r != s:
            res = min(res, dfs(r, d, P)+1)
    memo[s] = res
    return res

while 1:
    n = input()
    if n==0:
        break
    P = [raw_input().split() for i in xrange(n)]
    g = raw_input()
    d = raw_input()
    memo = {}
    res = dfs(g, d, P)
    print res if res < INF else -1

Solution (Python):


from collections import deque

while True:
    n = input()
    if n == 0:
        break
    dq = deque()

    lst = []
    for i in range(n):
        hoge = raw_input().split(" ")
        lst.append(hoge)
    gamma = raw_input()
    delta = raw_input()
    m = {}
    dq.append(gamma)
    num = 0
    while len(dq) > 0:
        sz = len(dq)
        for loop in range(sz):
            S = dq.popleft()
            if S in m:
                continue
            if len(S) > 10:
                continue
            m[S] = num
            for l in lst:
                SS = S.replace(l[0], l[1])
                dq.append(SS)
        num += 1
    
    if delta in m:
        print m[delta]
    else:
        print "-1"

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = [LS() for _ in range(n)]
        s = S()
        k = S()
        l = len(k)
        if s == k:
            rr.append(0)
            continue
        u = set([s])
        c = set([s])
        t = 0
        r = -1
        while c:
            t += 1
            ns = set()
            for cs in c:
                for d,e in a:
                    nt = cs.replace(d,e)
                    if len(nt) > l:
                        continue
                    ns.add(nt)
            if k in ns:
                r = t
                break
            c = ns - u
            u |= ns
        rr.append(r)

    return '\n'.join(map(str,rr))


print(main())

Solution (Python):
def substitute(text, a, b):
    pos = 0
    newText = text
    L1 = len(a)
    L2 = len(b)
    while True:
        idx = newText.find(a, pos)
        if idx < 0:
            return newText
        newText = newText[:idx] + b + newText[idx + L1:]
        pos = idx + L2
    return newText

def transform(orig, goal, count):
    global subs
    global minCount

    if len(orig) > len(goal):
        return

    if orig == goal:
        minCount = min(minCount, count)
        return
    
    for key in subs:
        newStr = substitute(orig, key, subs[key])
        if newStr != orig:
            transform(newStr, goal, count + 1)

if __name__ == '__main__':
    while True:
        N = int(input())
        if N == 0:
            break

        subs = {}
        for _ in range(N):
            a, b = input().strip().split()
            subs[a] = b
        
        orig = input().strip()
        goal = input().strip()

        minCount = 999999999
        transform(orig, goal, 0)

        if minCount == 999999999:
            print(-1)
        else:
            print(minCount)

Solution (Python):
from collections import deque

def testcase_ends():
    n = int(input())
    if n == 0:
        return 1

    sub = [input().split() for i in range(n)]
    gamma = input()
    delta = input()

    q = deque()
    q.append((gamma, 0))
    res = 10000
    while q:
        s, i = q.popleft()
        for alpha, beta in sub:
            if alpha not in s: continue

            t = s.replace(alpha, beta)
            if t == delta:
                res = min(res, i+1)
                continue
            elif len(t) >= len(delta):
                continue

            q.append((t, i+1))

    if res == 10000: res = -1
    print(res)
    return 0

def main():
    while not testcase_ends():
        pass

if __name__ == '__main__':
    main()

Solution (Python):

import queue
while 1:
    n=int(input())
    if n==0:
        break
    dic={}
    for i in range(n):
        k,s=input().split()
        dic[k]=s
    s=input()
    ans=input()
    q=queue.Queue()
    q.put((s,0))
    find=False
    while not q.empty():
        s=q.get()
        if s[0]==ans:
            print(s[1])
            q=queue.Queue()
            find=True
        if not find:
            for k in dic.keys():
                t=s[0].replace(k,dic[k])
                if len(t)<=len(ans) and s[0]!=t:
                    q.put((t,s[1]+1))
    if not find:
        print(-1)