学步园

题目大意:给出一个字符串,求其不包含两个长度为k的"重复串"的最长前缀.

对于任意串s,有

(1)大写字母与小写字母等价.

(2)串中所有字母个数定义为串的长度.

两个串s1,s2为长度为k的重复串,定义为:

(1)s1,s2长度均为k

(2)对于每个字母,在s1中出现次数等于在s2中出现次数.

hash一下随便搞搞就好了，字符串hash记录一下值对应的字符串就好了

千万别用(439,479,607,739,487,751,433,739,317,509,541,281,337,199,787,23,859,181,281,373,673,701,421,373,457,283)

来加密……随机100~maxn之间的数就好了

贡献了无数tle的人的忠告

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.