hud 3336 count the string (KMP)

这道题本来想对了，可是因为hdu对pascal语言的限制是我认为自己想错了，结果一看题解发现自己对了……

题意：给以字符串计算出以前i个字符为前缀的字符中在主串中出现的次数和
如： num(abab)=num(a)+num(ab)+num(aba)+num(abab)=2+2+1+1=6;
题解：next[i]记录的是长度为i 不为自身的最大首尾重复子串长度 num[i]记录长度为next[i]的前缀所重复出现的次数
推介一篇博文，非常不错，和本代码解法不一样，但实质上是一样的。

附上代码：

const mo=;

var sum,next:array[..] of longint;

    i,j,n,t,ans:longint;

    a:array[..] of char;

procedure main;

 begin

 fillchar(next,sizeof(next),);

 readln(n);

 readln(a);

 next[]:=-;

 i:=-;j:=;

 while j<n do

  if (i=-) or (a[i]=a[j]) then

   begin

    inc(i);inc(j);next[j]:=i;

   end

  else i:=next[i];

 ans:=;

 fillchar(sum,sizeof(sum),);

 for i:= to n do inc(sum[next[i]]);

 for i:= to n do

  ans:=(ans+sum[i]+) mod mo;

 writeln(ans);

 end;

begin

 readln(t);

 while t> do

  begin

   main;

   dec(t);

  end;

end.

 end;

要注意的 hdu不能用ansistring，必须用成array of char 不过读还是可以直接readln（a）；

另外再附一个完整的KMP的代码

var i,j,n,m,t:longint;

    next,a,b:array[..] of longint;

procedure main;

 begin

 readln(n,m);

 for i:= to n do read(a[i]);readln;

 for i:= to m do read(b[i]);

 fillchar(next,sizeof(next),);

 i:=;j:=;

 while j<m do

  if (i=) or (b[i]=b[j]) then

   begin

    inc(i);inc(j);next[j]:=i;

   end

  else i:=next[i];

 i:=;j:=;

 while (i<=m) and (j<=n) do

  if (i=) or (b[i]=a[j]) then

   begin

   inc(i);inc(j);

   end

  else i:=next[i];

 if i>m then writeln(j-m)

 else writeln(-);

 end;

begin

 readln(t);

 while t> do

  begin

  main;

  dec(t);

  end;

end.

这里面比较的是数。

巴特西

hud 3336 count the string (KMP)

最新文章

热门文章