kmp.pas

kmp算法的程序

program zju1073;
const
    maxn=70;
    cans:array[false..true] of string=(' is not cyclic',' is cyclic');

type
    num=array[0..maxn] of longint;

var
    s,st:string;
    sn:num;
    prefix:array[1..maxn] of longint;
    n,lens:longint;

procedure init;
var
    i:longint;
begin
    readln(st);
    n:=length(st);
    fillchar(sn,sizeof(sn),0);
    for i:=1 to n do sn[i]:=ord(st[n-i+1])-48;
    sn[0]:=n;
    while sn[sn[0]]=0 do dec(sn[0]);
    s:=st+st;
    lens:=length(s);
end;

procedure multiply(var x:num;m:longint);
var
    i:longint;
begin
    for i:=1 to x[0] do x[i]:=x[i]*m;
    for i:=1 to maxn-1 do
        if x[i]>=10 then
            begin
                inc(x[i+1],x[i] div 10);
                x[i]:=x[i] mod 10;
            end;
    x[0]:=maxn;
    while x[x[0]]=0 do dec(x[0]);
end;

procedure prekmp(x:string;len:longint);
var
    i,j:longint;
begin
    fillchar(prefix,sizeof(prefix),0);
    j:=0;
    for i:=2 to len do
        begin
            while (j>0) and (x[j+1]<>x[i]) do j:=prefix[j];
            if x[j+1]=x[i] then inc(j);
            prefix[i]:=j;
        end;
end;

function match(x:string;len:longint):boolean;
var
    i,j:longint;
begin
    j:=0;
    for i:=1 to lens do
        begin
            while (j>0) and (x[j+1]<>s[i]) do j:=prefix[j];
            if x[j+1]=s[i] then inc(j);
            if j=len then exit(true);
        end;
    exit(false);
end;

function check(x:num;m:longint):boolean;
var
    i:longint;
    s:string;
begin
    if m>1 then multiply(x,m);
    s:='';
    for i:=x[0] downto 1 do s:=s+chr(x[i]+48);
    prekmp(s,x[0]);
    if match(s,x[0]) then exit(true) else exit(false);
end;

procedure work;
var
    i:longint;
    flag:boolean;
begin
    flag:=true;
    for i:=1 to n do
        if not check(sn,i) then
            begin
                flag:=false;
                break;
            end;
    writeln(st,cans[flag]);
end;

begin
    while not eof do
        begin
            init;
            work;
        end;
end.