Abbreviation

Problem: Abbreviaton

We can solve this kind of string matching problem with dynamic programming, like Wildcard Matching and Regular Expression Matching

Code in Python:

import string

q = input()
for _ in xrange(q): 
    a = raw_input() 
    b = raw_input() 
    la, lb = len(a), len(b) 
    if lb > la: 
        print "NO" 
    dp = [[False] * (lb+1) for _ in xrange(la+1)] 
    dp[0][0] = True 
    for i in xrange(la): 
        if dp[i][0]: 
            dp[i+1][0] = True 
        for j in xrange(lb): 
            if dp[i][j] and a[i].lower() == b[j].lower(): 
                dp[i+1][j+1] = True 
            if dp[i][j+1] and a[i] in string.lowercase: 
                dp[i+1][j+1] = True 
    print "YES" if dp[-1][-1] else "NO"