1

入力を受け取り、大きな辞書テキストファイルで見つかったその入力の最初の順列を見つけて出力するlexコードを書き込もうとしています。これは私がこれまでに持っているものです：

%{
#include <stdio.h>
%}
%option noyywrap
%% 
INPUT GOES HERE { //Not sure what expression to put here 
    printf("Longest is: %s", yytext);
    return;
}

.|\n    {      }

%%

int main(void)
{
        yylex();
        return 0;
}

状態を使用する必要があると感じていますが、状態がどのように機能するかについてはあまり詳しくありません。誰かが私を正しい方向に向けることができますか？

編集：誰かがそれを望む場合に備えて、受け入れられた答えのコードは次のとおりです：

%{
#include <stdio.h>
#include <string.h>
%}
%option noyywrap
%% 
^[ablm]{4}$ { 
    char originalWord [5];
    strcpy(originalWord, yytext);
    char input[5] = {"ablm"};
    char tmp;
    int i, j;
    for(i=0; i<4; i++)
    {
        for (j=i+1; j<4; j++)
        {
            if (yytext[i] > yytext[j])
            {
                tmp=yytext[i];
                yytext[i]=yytext[j];    
                yytext[j]=tmp;
            }
        }
    }
    if(strcmp(input,yytext)==0){
        printf("First permutation is: %s", originalWord);
        return;     
    }
    else
        ;

}

.|\n    {      }

%%

int main(void)
{
        yylex();
        return 0;
}
4

2 に答える 2

2

正規表現は、「次の記号の順列」という形式の文字列の文字列照合をネイティブにサポートしない傾向があります。いくつかの文字列の順列に一致する正規表現を書くことができますが、そのためには (多かれ少なかれ) それらの文字のすべての順列を書き出してから、それらをすべて一緒に OR する必要があります。

これを行う簡単な方法は、適切な長さで、問題の文字列から取得した記号で構成されるすべての文字列に一致する正規表現を使用することです。次に、候補文字列を受け取るこの正規表現にアクションを関連付け、通常の C コードを使用して、文字列が元の文字セットの順列であるかどうかを判断できます。実際の辞書では誤検知の数は非常に少なく、候補の一致の処理にかかる時間はそれほど多くないため、これは非常に高速である必要があります。

お役に立てれば！

于 2013-02-03T01:04:38.550 に答える
1

なぜこのようなことに lex を使うのかよくわかりません。簡単で効率的なテスト方法は、辞書と入力に含まれる単語の文字を並べ替えることです (どのような並べ替え方法でも機能しますが、数え上げ並べ替えが適しています)。すべての順列は、同じ文字とそれらの文字の数を持たなければなりません。元の文字列を順列として数えたくない場合は、元の文字列ではないことをテストして確認してください。大きなディクショナリの場合、おそらく何らかのソートされたデータ構造を使用する必要があります。

ステート マシンは常に (理論的には) 順列を検証するように構築できますが、そのサイズは組み合わせによって大きくなります。「それら」のすべての順列を処理するための正規表現は次のようになります

meth|meht|mteh|mhet|mthe|mhte|emth|emht|tmeh|hmet|tmhe|hmte|etmh|ehmt|temh|hemt|thme|htme|ethm|ehtm|tehm|hetm|them|htem

または混在

m(e(th|ht)|t(he|eh)|h(te|et))|
e(m(th|ht)|t(hm|mh)|h(tm|mt))|
t(e(mh|hm)|m(he|eh)|h(me|em))|
h(e(tm|mt)|t(me|em)|m(te|et))
于 2013-02-03T01:25:35.883 に答える