regex - ある開始位置から文字列内のパターンの最初の出現を見つけるにはどうすればよいですか?

Question

任意の長さの文字列があり、位置 p0 から開始して、3 つの 3 文字パターンのうちの 1 つが最初に出現する場所を見つける必要があります。

文字列に文字のみが含まれていると仮定します。位置 p0 から始まり、'aaa' または 'bbb' または 'ccc' のいずれかが最初に出現するまで、トリプレットを前方にジャンプするトリプレットの数を見つける必要があります。

これは正規表現だけを使用しても可能ですか?

Answer 1

$string=~/^   # from the start of the string
            (?:.{$p0}) # skip (don't capture) "$p0" occurrences of any character
            (?:...)*?  # skip 3 characters at a time,
                       # as few times as possible (non-greedy)
            (aaa|bbb|ccc) # capture aaa or bbb or ccc as $1
         /x;

(p0 が 0 ベースであると仮定します)。

もちろん、文字列に substr を使用して前方にスキップする方がおそらく効率的です。

substr($string, $p0)=~/^(?:...)*?(aaa|bbb|ccc)/;

Answer 2

モリッツ氏は、これは正規表現よりも高速である可能性があると述べています。多少遅くても朝5時の方が分かりやすいです。:)

             #0123456789.123456789.123456789。  
my $string = "alsdhfaaasccclaaaagalkfgblkgbklfs";  
私の $pos = 9;  
私の $length = 3;  
私の $regex = qr/^(aaa|bbb|ccc)/;

while( $pos < 長さ $string )    
    {  
    print "$pos をチェック中\n";  

    if( substr( $string, $pos, $length ) =~ /$regex/ )
        {
        print "$pos で $1 が見つかりました\n";
        過去;
        }

    $pos += $length;
    }

Answer 3

正規表現で実際にカウントすることはできませんが、次のようなことができます:

pos $string = $start_from;
$string =~ m/\G         # anchor to previous pos()
            ((?:...)*?) # capture everything up to the match
            (aaa|bbb|ccc)
            /xs  or die "No match"
my $result = length($1) / 3;

しかし、substr() と unpack() を使用してトリプルに分割し、for ループでトリプルをウォークする方が少し速いと思います。

(編集: length() であり、length() ではありません;-)

Answer 4

速度が深刻な問題である場合は、3つの文字列が何であるかに応じて、ツリーを作成することで本当に凝ったものにすることができます（たとえば、Aho-Corasickアルゴリズムなど）。

考えられるすべての状態のマップが可能です。たとえば、'a'で始まる文字列がない場合はstate[0] ['a']=0です。

Answer 5

これの主要部分は分割 /(...)/ です。しかし、これが終わると、位置と発生データが得られます。

my @expected_triplets = qw<aaa bbb ccc>;
my $data_string      
    = 'fjeidoaaaivtrxxcccfznaaauitbbbfzjasdjfncccftjtjqznnjgjaaajeitjgbbblafjan'
    ;
my $place          = 0;
my @triplets       = grep { length } split /(...)/, $data_string;
my %occurrence_for = map { $_, [] } @expected_triplets;
foreach my $i ( 0..@triplets ) {
    my $triplet = $triplets[$i];
    push( @{$occurrence_for{$triplet}}, $i ) if exists $occurrence_for{$triplet};
}

または、正規表現による単純なカウント用 (Experimental (??{}) を使用)

my ( $count, %count );
my $data_string      
    = 'fjeidoaaaivtrxxcccfznaaauitbbbfzjasdjfncccftjtjqznnjgjaaajeitjgbbblafjan'
    ;
$data_string =~ m/(aaa|bbb|ccc)(??{ $count++; $count{$^N}++ })/g;