Golf String's format() inverse
Haskell, 220 characters

import Data.Map;f""""=[empty]
f('{':b)d=[insert k m b|(k,('}':a))&lt;-lex b,(m,c)&lt;-[splitAt n d|n&lt;-[0..length d]],b&lt;-f a c,notMember k b||b!k==m]
f(x:b)(y:d)|x==y=f b d;f _ _=[];format1 x y=elems$mapKeys((0+).read)$f x y!!0


Breaks if you use multiple representations for the same pattern ({1} vs {01}) - doesn't enforce their equality, discarding matches for all but one representation instead.

19 characters can be saved by omiting mapKeys((0+).read)$ if proper ordering of matches above 10 patterns doesn't matter, or if padding to the same length may be required, or if string ordering of patterns is acceptable. In any case, if a pattern is omitted from the first argument, it is omitted from the result as well.

Removing !!0 from the end makes format1 return the list of all solutions, rather than just the first one.

before golfing:

import Data.Map
import Control.Monad

cuts :: [a] -&gt; [([a],[a])]
cuts a=[splitAt n a | n &lt;- [0..length a]]

f :: String -&gt; String -&gt; [Map String String]
-- empty format + empty parsed = one interpretation with no binding
f "" "" = [empty]
-- template-start format + some matched = branch search
f ('{':xs) ys = do
    let [(key, '}':xr)] = lex xs
    (match, yr) &lt;- cuts ys
    b &lt;- f xr yr
    guard $ notMember key b || b!key == match
    return $ insert key match b
-- non-empty format + matching parsed = exact match
f (x:xs) (y:ys) | x == y = f xs ys
-- anything else = no interpretation
f _ _ = []

deformat :: String -&gt; String -&gt; [String]
deformat x y = elems $ mapKeys ((0+).read) $ head $ f x y