正規表現でCommon Prefix Searchを行う力技な方法のPerlによるサンプル。
ちょっと試すとき用のコピペ用コード片、といった感じのものです。
TRIEとかオートマトンとかでちゃんとやるのが王道ですよ。

コード：

use strict;
use warnings;
use utf8;
binmode STDOUT, ":utf8";
my $str = "あうえういあおういいういああ";
my $key = "ういあ";
my @chars = split("", $key);
my $pat = join("(", @chars).(")?" x $#chars);
while ($str =~ /($pat)/g) {
    print "$1\n";
}

実行例：

% perl a.pl
う
ういあ
うい
ういあ