首页 / 更多教程 / hud 3336 count the string (KMP)

hud 3336 count the string (KMP)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了hud 3336 count the string (KMP)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1460字，纯文字阅读大概需要3分钟。

内容图文

这道题本来想对了，可是因为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=10007;
var sum,next:array[0..200000] of longint;
    i,j,n,t,ans:longint;
    a:array[0..200000] of char;
procedure main;
 begin
 fillchar(next,sizeof(next),0);
 readln(n);
 readln(a);
 next[0]:=-1;
 i:=-1;j:=0;
 while j<n doif (i=-1) or (a[i]=a[j]) thenbegin
    inc(i);inc(j);next[j]:=i;
   endelse i:=next[i];
 ans:=0;
 fillchar(sum,sizeof(sum),0);
 for i:=1to n do inc(sum[next[i]]);
 for i:=1to n do
  ans:=(ans+sum[i]+1) mod mo;
 writeln(ans);
 end;
begin
 readln(t);
 while t>0dobegin
   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[0..1000100] of longint;
procedure main;
 begin
 readln(n,m);
 for i:=1to n do read(a[i]);readln;
 for i:=1to m do read(b[i]);
 fillchar(next,sizeof(next),0);
 i:=0;j:=1;
 while j<m doif (i=0) or (b[i]=b[j]) thenbegin
    inc(i);inc(j);next[j]:=i;
   endelse i:=next[i];
 i:=1;j:=1;
 while (i<=m) and (j<=n) doif (i=0) or (b[i]=a[j]) thenbegin
   inc(i);inc(j);
   endelse i:=next[i];
 if i>m then writeln(j-m)
 else writeln(-1);
 end;
begin
 readln(t);
 while t>0dobegin
  main;
  dec(t);
  end;
end.

这里面比较的是数。

原文：http://www.cnblogs.com/zyfzyf/p/3766345.html

内容总结

以上是互联网集市为您收集整理的hud 3336 count the string (KMP)全部内容，希望文章能够帮你解决hud 3336 count the string (KMP)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1075632.html

来源：【匿名】