记录编号	39207	评测结果	AAAAAAAAAA
题目名称	解密	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	1.818 s
提交时间	2012-07-06 17:24:19	内存使用	19.76 MiB

type pa=^pb;
pb=record
 s1:ansistring;
 dd:longint;
 n:pa;
 end;
var
 a,b,next1,f,next2:array[0..1000000] of longint;
 hash:array[0..137730] of pa;
 i,j,m,n,tt,n1,n2,sum1:longint;
 ch:char;
 s:string;
 function insert(s:string):longint;
 var date:int64;o:boolean;p,pv:pa;i:longint;
 begin
  date:=1;
  for i:=1 to length(s) do
   date:=(date mod 137731)*(date mod 137731)*ord(s[i]) mod 137731;
  p:=hash[date];
  while p<>nil do
   begin
    if s=p^.s1 then break;
    p:=p^.n;
   end;
  if p<>nil then insert:=p^.dd else
   begin
    inc(tt);
    new(pv);
    pv^.s1:=s;
    pv^.dd:=tt;
    pv^.n:=hash[date];
    hash[date]:=pv;
    insert:=tt;
   end;
 end;
function macth(x,y:longint):boolean;
var t:longint;
 begin
  t:=next1[x];
  if y+t>n2 then t:=0;
  if t=next2[y] then macth:=true else macth:=false;
 end;
begin
 assign(input,'kriptogram.in');reset(input);
 assign(output,'kriptogram.out');rewrite(output);
 randomize;
 while not eoln do
  begin
   inc(i);
   s:='';
   repeat
    read(ch);
    if ch='$' then break;
    s:=s+ch;
   until ch=' ';
  if ch='$' then break;
  a[i]:=insert(s);
  end;
 readln;
 n1:=i-1;tt:=0;
 for i:=0 to 137730 do  hash[i]:=nil;
 i:=0;
 while not eoln do
  begin
   inc(i);
   s:='';
   repeat
    read(ch);
    if ch='$' then break;
    s:=s+ch;
   until ch=' ';
  if ch='$' then break;
  b[i]:=insert(s);
  end;
 n2:=i-1;
 for i:=1 to n1 do
  begin
   next1[f[a[i]]]:=i-f[a[i]];
   f[a[i]]:=i;
  end;
 fillchar(f,sizeof(f),0);
 for i:=1 to n2 do
  begin
   next2[f[b[i]]]:=i-f[b[i]];
   f[b[i]]:=i;
  end;
 f[0]:=0;f[1]:=0;
 for i:=2 to n2 do
  begin
    while (j>0) and (next2[i]<>next2[j+1]) do j:=f[j];
    if  next2[j+1]=next2[i]  then inc(j);
    f[i]:=j;
  end;
  j:=0;
 for i:=1 to n1 do
  begin
    while (j>0) and  not macth(i,j+1)   do j:=f[j];
    if  macth(i,j+1) then inc(j);
    if  j=n2 then begin writeln(i-j+1); break; end;
  end;
 close(input);close(output);
 end.