关于正则表达式文件匹配有关问题
关于正则表达式文件匹配问题
找出一个最优正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件，所找出的正则表达式的长度还应是最短的。
由文件input.txt 提供输入数据。文件由n（1≤n≤250）行组成。每行给出一个文件名。文件名由英文字母 和数字组成。英文字符要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，“-”表示不进行操作。
实在不懂，请各位指教！
分析如下：
由于在目录下的文件制定，因此很难确定一种能直接寻找最优正则表达式的解析方法，在这种情况下，势必采取回溯法：从空串出发出发，从可选字符集中挑选字符式填入当前正则式，并计算所能匹配的待操作文件数。在搜索了正则表达式左右可能形式后，辨得出匹配的待操作文件数最多且长度最短的一个表达式。设：
bestm---最优正则表达式所能匹配的到操作文件数，初始值巍0；
best1---最优表达式的长度，初始值为9（最优表达式的长度最大为8）；
len---当前正则表达式的长度，初始值为0；
match---可能被匹配的最多文件数，初始值设为带操最文件数；
del---第i个文件可能被当前正则表达式的扩展形式（正则表达式*）所匹配的标志。
del[i]= 0,第i个文件可能被匹配；
≠0,第i个文件不可能被匹配。
初始时，所有文件设置为可能匹配标志。在搜索过程中，某个文件j（1≤j≤n）不能匹配当前正则表达式*，则说明当前正则表达式无论怎样延伸，文件j都不可能与其匹配，因此取消文件的可能匹配标志（使del[j] ≠0）。如果文件j为一个待操作，则match-1。设置match这个变量为了设置搜索槛值和递归边界的需要，每增加正则表达式一个字符时，如果发现match<bestm，或者match=bestm，但是当前正则表达式的长度len≥best1，则放弃，因为它不可能构成最优。递归搜索的前提条件是Match<>0。否则，当前正则表达式无一可匹配的待操作文件，自然也就失去了递归搜索的下一个字符的必要。
同样，在搜索的过程中，如果发现一个可能被匹配的不进行操作文件i(del[i]=0)能与当前正则表达式匹配，则断定当前正则表达式非法，因为要找的正则表达式不能匹配任何不能够操作的文件。
3、回溯搜索的过程有一个称谓Run的递归算法描述：
Produce Run(Len);
begin
if Len>0 then
begin
搜索所有可能匹配（del值为0）且匹配当前正则表达式的文件
if 所有文件为待操作文件
then begin
计算匹配的文件数j;
if(j>bestm) or (j=bestm) and (len<best1)
then begin
当前正则表达式作为最优方案记录如下;
bestm ← J;best1 ← len;exit
end;{then}
end;{then}
end;{then}
len ← len-1;
if(Match<bestm)or(len>8)or(Match=bestm)and(len≥best1)then exit;
for i:=1 to 可选字符集的字符个数 do
if(len=1)or(可选字符集第i个的字符<>'*')or
(当前正则表达式的第len-1个字符非'*'或'?')
then begin
可选字符集的第i个字符集进入当前正则表达式;
搜索所有文件，取消不能够匹配当前正则表达式*的文件的可能的匹配标志，
Match减去它们中间带操作文件的数量；
if match<>0 then Run(len);
恢复递归前所有文件的del值、match值和正则表达式长度；
end;{then}
end;{Run}
------解决方案--------------------
这是很古老的一道noi题了。看不懂说明还没到火候，先看别的题熟悉搜索算法以后再看这个。
------解决方案--------------------
提问的智慧
找出一个最优正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件，所找出的正则表达式的长度还应是最短的。
由文件input.txt 提供输入数据。文件由n（1≤n≤250）行组成。每行给出一个文件名。文件名由英文字母 和数字组成。英文字符要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，“-”表示不进行操作。
实在不懂，请各位指教！
分析如下：
由于在目录下的文件制定，因此很难确定一种能直接寻找最优正则表达式的解析方法，在这种情况下，势必采取回溯法：从空串出发出发，从可选字符集中挑选字符式填入当前正则式，并计算所能匹配的待操作文件数。在搜索了正则表达式左右可能形式后，辨得出匹配的待操作文件数最多且长度最短的一个表达式。设：
bestm---最优正则表达式所能匹配的到操作文件数，初始值巍0；
best1---最优表达式的长度，初始值为9（最优表达式的长度最大为8）；
len---当前正则表达式的长度，初始值为0；
match---可能被匹配的最多文件数，初始值设为带操最文件数；
del---第i个文件可能被当前正则表达式的扩展形式（正则表达式*）所匹配的标志。
del[i]= 0,第i个文件可能被匹配；
≠0,第i个文件不可能被匹配。
初始时，所有文件设置为可能匹配标志。在搜索过程中，某个文件j（1≤j≤n）不能匹配当前正则表达式*，则说明当前正则表达式无论怎样延伸，文件j都不可能与其匹配，因此取消文件的可能匹配标志（使del[j] ≠0）。如果文件j为一个待操作，则match-1。设置match这个变量为了设置搜索槛值和递归边界的需要，每增加正则表达式一个字符时，如果发现match<bestm，或者match=bestm，但是当前正则表达式的长度len≥best1，则放弃，因为它不可能构成最优。递归搜索的前提条件是Match<>0。否则，当前正则表达式无一可匹配的待操作文件，自然也就失去了递归搜索的下一个字符的必要。
同样，在搜索的过程中，如果发现一个可能被匹配的不进行操作文件i(del[i]=0)能与当前正则表达式匹配，则断定当前正则表达式非法，因为要找的正则表达式不能匹配任何不能够操作的文件。
3、回溯搜索的过程有一个称谓Run的递归算法描述：
Produce Run(Len);
begin
if Len>0 then
begin
搜索所有可能匹配（del值为0）且匹配当前正则表达式的文件
if 所有文件为待操作文件
then begin
计算匹配的文件数j;
if(j>bestm) or (j=bestm) and (len<best1)
then begin
当前正则表达式作为最优方案记录如下;
bestm ← J;best1 ← len;exit
end;{then}
end;{then}
end;{then}
len ← len-1;
if(Match<bestm)or(len>8)or(Match=bestm)and(len≥best1)then exit;
for i:=1 to 可选字符集的字符个数 do
if(len=1)or(可选字符集第i个的字符<>'*')or
(当前正则表达式的第len-1个字符非'*'或'?')
then begin
可选字符集的第i个字符集进入当前正则表达式;
搜索所有文件，取消不能够匹配当前正则表达式*的文件的可能的匹配标志，
Match减去它们中间带操作文件的数量；
if match<>0 then Run(len);
恢复递归前所有文件的del值、match值和正则表达式长度；
end;{then}
end;{Run}
正则表达式
文件匹配
回溯法
------解决方案--------------------
这是很古老的一道noi题了。看不懂说明还没到火候，先看别的题熟悉搜索算法以后再看这个。
------解决方案--------------------
提问的智慧