Part 1:

# 39 chars
sub f {
  #23456789_123456789_
  my($p,$d)=@_;$p=~tr
  /_/./;grep/^$p$/,@$d
}
[download]

Part 1 with E/C:

# 60 chars
sub f {
  #23456789_123456789_123456789_
  my($p,$d)=@_;my@c=$p=~/[^_]/g;
  $p=~s/_/[^@c]/g;grep/^$p$/,@$d
}
[download]

Part 2:

# 123 chars
sub g {
  #23456789_123456789_123456789_123456789_12
  my($p,$d,@l)=@_;$p=~s/_/[^@l]/g;$_=join''
  ,sort+map{split//}grep/$p/i&&s/[@l]//g,@$d
  ;$p=y;;;c;/(.)\1{$p}/&&return$1while--$p
}
[download]

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker.
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;