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

正则表达式本身并不倾向于支持“以下符号的某些排列”形式的字符串的字符串匹配。您可以编写匹配某些字符串排列的正则表达式，但要这样做，您（或多或少）必须写出这些字符的所有排列，然后将它们全部组合在一起。

一个更简单的方法是使用一个正则表达式来匹配所有具有适当长度的字符串，并且这些字符串由从相关字符串中提取的符号组成。然后，您可以将一个动作与该正则表达式相关联，该正则表达式将接收候选字符串，然后使用普通 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 回答