Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这么长,恐怖

Posted by frkstyc at 2005-06-19 19:22:51 on Problem 2406
In Reply To:程序如下 Posted by:zhougelin at 2005-06-19 19:02:26
> program pku2406;
> const inputfilename='';
>       outputfilename='';
>       maxlen=1000005;
> var len:longint;
>     data:array[1..maxlen]of char;
>     ext :array[1..maxlen]of longint;
>     chk :array[1..maxlen]of boolean;
>     buf :array[0..1 shl 18]of byte;
> function read_data:boolean;
> var ch:char;
> begin
>       len:=0;
>       while not seekeoln do
>       begin
>         read(ch);
>         len:=len+1;
>         data[len]:=ch;
>       end;
>       read_data:=(len>1) or (data[1]<>'.');
>       if read_data then readln;
> end;
> procedure proceed;
> var i,j,k,max,l:longint;
> begin
>       if len=1 then begin writeln(1); exit; end;
>       ext[1]:=len;
>       j:=0;
>       while (j+2<=len) and (data[j+1]=data[j+2]) do
>         j:=j+1;
>       ext[2]:=j;k:=2;
>       for i:=3 to len do
>       begin
>          chk[i]:=false;
>          max:=ext[k]+k-1;l:=ext[i-k+1];
>          if l<max-i+1 then ext[i]:=l else
>          begin
>            if max-i+1>0 then j:=max-i+1 else j:=0;
>            while (j+i<=len) and (data[j+1]=data[j+i]) do
>              j:=j+1;
>            ext[i]:=j;k:=i;
>          end;
>       end;
>       chk[1]:=false;chk[2]:=false;
>       ext[len+1]:=0;
>       for i:=1 to len do
>          if not chk[i] then
>          begin
>            j:=len-i+1;
>            while ext[j]=ext[j+i]+i do
>            begin
>              chk[j]:=true;
>              j:=j-i;
>              if j<=0 then break;
>            end;
>            if j=-i+1 then
>            begin
>              writeln(len div i);
>              break;
>            end;
>          end;
> end;
> begin
>       assign(input,inputfilename);
>       settextbuf(input,buf);
>       reset(input);
>       assign(output,outputfilename);
>       rewrite(output);
>       while read_data do
>         proceed;
>       close(input);
>       close(output);
> end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator