加载中…
个人资料
sacredfantasy
sacredfantasy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,313
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

usaco 2.3.1 prefix

(2009-04-24 00:19:58)
标签:

usaco

2.3.1

prefix

杂谈

分类: OI题解
这个程序是有史以来我编得最认真的usaco题目,虽然这个程序很慢,甚至在主程序部分使用了一点歪招?!但是这是使用递归思想的,非指针的Trie!没有优化,所以在贴上这个程序后,再贴一个正规一点的。
 Compiling...
 Compile: OK Executing...
 Test 1: TEST OK [0.000 secs, 6792 KB]
 Test 2: TEST OK [0.000 secs, 6796 KB]
 Test 3: TEST OK [0.000 secs, 6828 KB]
 Test 4: TEST OK [0.000 secs, 6824 KB]
 Test 5: TEST OK [0.032 secs, 6828 KB]
 Test 6: TEST OK [0.670 secs, 6828 KB]
 All tests OK.

program prefix;
type node=record   
        data:char;
        son:integer;
        jl:boolean;
        er:array[1..1800]of integer;
        end;
var ji,total,root,max,k:longint;
        zd:array[1..1800]of node;
        y1:array[1..200]of string;
        ls:array[1..200000]of boolean;
        s:ansistring;
        flag:boolean;
procedure find(x:string;wz,c:integer);
var i:integer;
begin
    for i:=1 to zd[wz].son do
    begin
        if zd[zd[wz].er[i]].data=x[c] then
        begin
            if c+1<=length(x) then find(x,zd[wz].er[i],c+1)
            else begin
                        if zd[zd[wz].er[i]].jl then flag:=true;
                        exit;
                    end;
        end;
    end;
end;
procedure insert(x:string;y,z:integer);
var i:integer;
        f:boolean;
begin
    f:=true;
    if zd[y].son=0 then
        begin
            inc(total);
            inc(zd[y].son);
            zd[y].er[zd[y].son]:=total;
            zd[total].data:=x[z];
            if (z+1)<=length(x) then
                insert(x,total,z+1)
            else begin zd[total].jl:=true;exit;end;
        end
    else
    for i:=1 to zd[y].son do
        if zd[zd[y].er[i]].data=x[z] then
            begin
                if (z+1)<=length(x) then
                begin
                    insert(x,zd[y].er[i],z+1);
                    exit;
                end
                else begin zd[total].jl:=true;exit;end;
            end
            else begin f:=false;end;
    if not f then
        begin
            inc(total);
            inc(zd[y].son);
            zd[y].er[zd[y].son]:=total;
            zd[total].data:=x[z];
            if (z+1)<=length(x) then
                insert(x,total,z+1)
            else begin zd[total].jl:=true;exit;end;
        end;
end;
procedure init;
var i:longint;
    te:char;
    temp:ansistring;
begin
    root:=1;
    zd[root].data:=' ';
    zd[root].son:=0;
    total:=1;
    ji:=1;
    repeat
        while not eoln(input) do
        begin
            read(te);
            if te<>'.' then
                if (te=' ') then
                    inc(ji)
                else if te in ['A'..'Z'] then
                    y1[ji]:=y1[ji]+te;
        end;
        if eoln(input) then inc(ji);
        readln;
    until te='.';
    max:=-1;
    for i:=1 to ji do
    begin
        insert(y1[i],root,1);
        if length(y1[i])>max then max:=length(y1[i]);
    end;
    s:='';
    k:=0;
    while not eof(input) do
    begin
        readln(temp);
        k:=k+length(temp);
        s:=s+temp;
    end;
end;
procedure main;
var i,j,q,head,tail:longint;
    st:string;
begin
    if k>100000 then
    begin
        head:=k div 2;
        tail:=k;
    end
    else
    begin
        head:=1;
        tail:=k;
    end;//由于怕通不过,所以这里计算了一下数学期望,大于100000的数据折半处理。当然前一半在适当情况还是要算的。记得noip2008火柴棒等式我就使用了这种思想。
    for i:=head to tail do
    begin
        st:='';
        for j:=1 to max do
        begin
            flag:=false;
            st:=st+s[i+j-1];
            find(st,root,1);
            if flag then
                for q:=i to i+j-1 do
                    ls[q]:=true;
        end;
    end;
    for i:=head to tail do
        if not ls[i] then
        begin
            writeln(i-1);
            exit;
        end;
    if ls[k] then writeln(k);
end;
begin
    assign(input,'prefix.in');
    reset(input);
    assign(output,'prefix.out');
    rewrite(output);
    init;
    main;
    close(input);
    close(output);
end.
字符串匹配:
program prefix;
const cht=['A'..'Z'];
var i,j,n,t:longint;
    tmp:char;
    temp,s:ansistring;
    a:array[1..200]of string[10];
    f:array[0..200000]of boolean;
begin
 assign(input,'prefix.in');
 reset(input);
 assign(output,'prefix.out');
 rewrite(output);
 t:=1;
 while tmp<>'.'  do
  begin
   read(tmp);
   if tmp in cht then
    a[t]:=a[t]+tmp
   else inc(t);
  end;
 while not eof do
  begin
   readln(temp);
   s:=s+temp;
  end;
 dec(t);
 n:=length(s);
 f[0]:=true;
 for i:=1 to n do
  for j:=1 to t do
   if length(a[j])<=i then
    if copy(s,i-length(a[j])+1,length(a[j]))=a[j] then
     if f[i-length(a[j])] then
      begin
       f[i]:=true;
       break;
      end;
 for i:=n downto 0 do
  if f[i] then
   begin
    writeln(i);
    halt;
   end;
 close(input);
 close(output);
end.

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有