【高分】关于字符串匹配（通配符）的问题。

很多操作系统都采用正则表达式来实现文件匹配功能。一种简单的正则表达式是由英文字母（区分大小写）、数字及通配符“*”和“?”任意组合而成的。“?”代表任意一个字符，“*”代表零个或任意多个字符。例如，a*b可以匹配acb,aabb,afdfdb,ab等，但不可以匹配ac,bb,abbc；a?b可以匹配acb,abb,但不可以匹配ab,accb。现要对某目录下的部分文件进行操作，试编写一个程序，寻找一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。注意你所找到的最优正则表达式的长度应当是最短的。如果有多个长度最短的最优正则表达式，只需输出其中的任意一个。输入以正文文件形式（STRING.TXT，见附一），每行给出了一个文件名（由英文字母和数字组成，英文字符要区分大小写），其后是一个空格符和一个字符(+或－)，“+”表示要对该文件进行操作，“-”表示不进行操作。输出你所找到的最优正则表达式和其能匹配的文件名数目。（NOI 97）
附一 STRING.TXT:
aacg +
aabcg -
abcg + a
bcdfg + a
dcfcsg +
adcfcsh -
adcgh + a
aacf -
alcccccg +
alcccccddg +
alcddeeeeffg +
bacg –

10 个解决方案

#1

大家不要被题目长度所迷惑，至少思路能给一些吧？？这是NOI97的一道题

#2

program noi97;

type

  List=^Tlist;

  TList=record

    num:Integer;

    next:List;

  end;

  Node=^TNode;

  Tnode=record

    St:String;

{    Ch:List;}

    N1,N2:integer;

    S:Array[1..250] of integer;//原题是<=250

    Next:Node;

  end;

const

  C:String='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890*?';

var

  Data:array[1..250] of String;

  Ok:array[1..250] of boolean;

  n:integer;

  Head,Tail,NewNode:Node;

  quit:boolean;

  k:integer;

  max:Integer;

  readn:integer;

procedure init;

var

  k:Integer;

  f:Text;

begin

  assign(f,'input.006'); reset(f);

  readln(f,n);

  new(head); Head^.St:=''; Head^.Next:=nil;

  Head^.N1:=0; Head^.N2:=0;

  Tail:=Head;

  for k:=1 to n do begin

    readln(f,data[k]);

    Head^.S[k]:=k;

    if data[k,length(data[k])]='+' then begin

      ok[k]:=true;

      inc(head^.N1);

    end else begin

      ok[k]:=false;

      inc(head^.N2);

    end;

    delete(data[k],length(data[k])-1,2);

  end;

  close(f);

end;

procedure compare(S1,S2:string;var same:boolean);//这个地方有点错！

var

  i,j:integer;

  k:Integer;

  quit:boolean;

begin

  i:=1; j:=1;

  quit:=false;

  repeat

    if (i>Length(S1)) then begin

      quit:=true;

      break;

    end;

    if (S1[i]='*') then begin

      for k:=j to length(s2) do

        if (s1[i+1]=S2[k]) then begin

          compare(copy(S1,i+2,Length(S1)-i-1),Copy(S2,k+1,length(S2)-k),quit);

          if quit then begin

            same:=true; exit;

          end;

        end;

      if not quit then

        if Length(S1)=i then begin

        same:=true; exit;

        end else begin

        same:=false; exit;

        end;

    end;

    if (S1[i]='?') then begin

      inc(i); inc(j);

      if j>Length(S2) then begin

        same:=false;

        exit;

      end;

    end else if (S1[i]=S2[j]) then begin

      inc(i); inc(j);

    end else begin

      same:=false; exit;

    end;

  until quit;

  same:=true;

end;

function Left(C:char):Boolean;

var

  k:integer;

  Same:Boolean;

  total:integer;

begin

  NewNode^.N1:=0; NewNode^.N2:=0;

  NewNode^.St:=Tail^.st+C;

  total:=0;

  Left:=false;

  for k:=1 to Tail^.N1+Tail^.N2 do begin

    compare(Tail^.St+C,Data[Tail^.S[k]],Same);

    if Same then begin

      inc(total);

      Left:=True;

      NewNode^.S[total]:=Tail^.S[k];

      if Ok[Tail^.S[k]] then begin

        inc(NewNode^.N1);

      end else begin

        inc(NewNode^.N2);

      end;

    end;

  end;

  if NewNode^.N1=0 then Left:=false;

end;

begin

  init;

  quit:=False; max:=0; readn:=0;

  New(NewNode); NewNode^.next:=nil;

  repeat

    for k:=1 to 62 do if Left(C[k]) then begin

      if NewNode^.N2=0 then begin

        if NewNode^.N1>=max then writeln(NewNode^.N1,' ',NewNode^.St);

        inc(readn);

{        if readn mod 15=0 then readln;}

        if NewNode^.N1>max then max:=NewNode^.N1;

      end;

      if NewNode^.N1>max then begin

        Head^.Next:=NewNode;

        Head:=Head^.Next;

        New(NewNode); NewNode^.next:=nil;

      end;

    end;

    if (Tail^.St[Length(Tail^.St)]<>'*') then

      for k:=63 to 64 do if Left(C[k]) then begin

        if NewNode^.N2=0 then begin

        if NewNode^.N1>=max then writeln(NewNode^.N1,' ',NewNode^.St);

        inc(readn);

{       if readn mod 15=0 then readln;}

        if NewNode^.N1>max then max:=NewNode^.N1;

        end;

        if NewNode^.N1>max then begin

        Head^.Next:=NewNode;

        Head:=Head^.Next;

        New(NewNode); NewNode^.next:=nil;

        end;

      end;

    if Tail^.next<>nil then Tail:=Tail^.next

      else break;

  until quit;

end.

#3

哇～～～遇上高手啦！
能不能给一点说明呢？如果你手头有题目解析的话。

#4

手头没解题报告。复制的。
OIBH没么？去搜搜吧。

#5

感觉BFS或DP都可以吧。

#6

OIBH没有耶
能再说得详细些吗？

#7

以前好象在国家集训队论文里有看到过.具体是谁的，我也忘了.此题我也没做过:-(

#8

上面源码中的compare是什么功能？它与判断一个正则表达式与一个字符串是否匹配的功能应该略有差别吧？
你说那里面有点错，请问指的是哪里？

#9

再保留一天吧，各位再提提意见，然后就结贴。

#10

那个compare函数只是会导致输出时会遗漏最后一个*,你加一个控制条件改改就行。主要是在
用length判断的地方

#1