Here's my shot at it; 68 chars:
sub c { ($_,$a)=@_; map{$h{$_}?$h{$_}:do{$h{$_}=(split//,$a)[$i++]."\0"}}/./g }


Here's another at 66. This one takes a completely different approach--it removes all duplicates of letters(the long part), then does a simple translation on them (the easy part). Here it is:

sub c { ($_,$a)=@_;$b=$_; 1 while$b=~s/(.)(.*?)\1/$1$2/g; eval"y/$b/$a/"; $_ }

Update2:Good catch tilly. This makes it too long to contend, but here's the revised version:

sub c { ($_,$a)=@_;$b=$_; 1 while$b=~s/(.)(.*?)\1/$1$2/g; eval"y/\Q$b\E/\Q$a\E/"; $_ }

The 15 year old, freshman programmer,
Stephen Rawls

In reply to Re: (Golf) Cryptographer's Tool #1 by srawls
in thread (Golf) Cryptographer's Tool #1 by Masem

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":