首页 > 代码库 > hud 3336 count the string (KMP)
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=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 do if (i=-1) or (a[i]=a[j]) then begin inc(i);inc(j);next[j]:=i; end else i:=next[i]; ans:=0; fillchar(sum,sizeof(sum),0); for i:=1 to n do inc(sum[next[i]]); for i:=1 to n do ans:=(ans+sum[i]+1) mod mo; writeln(ans); end; begin readln(t); while t>0 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[0..1000100] of longint; procedure main; begin readln(n,m); for i:=1 to n do read(a[i]);readln; for i:=1 to m do read(b[i]); fillchar(next,sizeof(next),0); i:=0;j:=1; while j<m do if (i=0) or (b[i]=b[j]) then begin inc(i);inc(j);next[j]:=i; end else i:=next[i]; i:=1;j:=1; while (i<=m) and (j<=n) do if (i=0) 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(-1); end; begin readln(t); while t>0 do begin main; dec(t); end; end.
这里面比较的是数。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。