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

= =这道题hash方程用到的的数随机即可,千万不要用百度搜到的第一个那个人用的hash方程

Posted by weixinding at 2012-03-11 11:30:50 on Problem 2119
随便加密了下然后记录hash值对应的字符串就行了O(nk)
我怎么想都超不了时……但就是tle,下了数据发现确实很慢,看了下发现每个字符串hash值浮动特别小,随机了个下hash方程轻松跑完……

贴个程序

program poj2119;
const
  maxn=999997;
var
  n,ans,i,j,k,o:longint;
  loop:char;
  s,t:ansistring;
  sp:array ['a'..'z'] of longint;
  con:array ['a'..'z'] of longint;
  map:array [0..100001] of longint;
  rehash:array [0..maxn] of string[50];
  count:array [0..maxn] of longint;

function hash (o:longint):longint;inline;
var
  i,k:longint;
  loop:char;
  now:string;
begin
  k:=0;
  now:='';
  for loop:='a' to 'z' do
    begin
      k:=(k+con[loop]*sp[loop]) mod maxn;
      for j:=1 to con[loop] do
        now:=now+loop;
    end;
  while (count[k]<>0)and(rehash[k]<>now) do
    begin
      inc(k);
      if k=maxn then k:=0;
    end;
  rehash[k]:=now;
  exit(k);
end;

begin
  randomize;
  for loop:='a' to 'z' do
    sp[loop]:=random(maxn-100)+90;
  repeat
    readln(k);
    if k=0 then break;
    fillchar(count,sizeof(count),0);
    fillchar(con,sizeof(con),0);
    readln(s);
    ans:=length(s);
    t:='';
    n:=0;
    for i:=1 to ans do
      if (s[i]>='A')and(s[i]<='Z') then
        begin
          t:=t+chr(ord(s[i])+32);
          inc(n);
          map[n]:=i;
        end
                                   else
      if (s[i]>='a')and(s[i]<='z') then
        begin
          t:=t+s[i];
          inc(n);
          map[n]:=i;
        end;
    if n<k then
      begin
        writeln(ans);
        continue;
      end;
    for i:=1 to k-1 do
      inc(con[t[i]]);
    for i:=k to n do
      begin
        inc(con[t[i]]);
        if i>k then dec(con[t[i-k]]);
        j:=hash(i);
        inc(count[j]);
        if count[j]=2 then
          begin
            ans:=map[i]-1;
            break;
          end;
      end;
    writeln(ans);
  until false;
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