首页 > 代码库 > BZOJ1030 [JSOI2007]文本生成器
BZOJ1030 [JSOI2007]文本生成器
搬运以前的题解中：
此题一看60个模式串，就知道是AC自动机。
最后要求含有模式串的个数，也就是（全部的个数 - 不含模式串的个数）。
于是就是裸的AC自动机上做DP了，再一看，m <= 100, 真是良心题，还不用矩阵优化。
这里有一个trick：在建自动机的时候要搞清楚哪些状态是无效的，我忘了加一句话（line 51）然后WA了两次。。。
于是开始复习（重新学习）AC自动机。。。各种悲剧。。。总算A掉了
1 const 2 prime : longint = 10007; 3 4 var 5 q, fai : array[0..10000] of longint; 6 tail : array[0..10000] of boolean; 7 tr : array[0..7000, 0..30] of longint; 8 f : array[0..110, 0..6100] of longint; 9 i, n, m, tot, len, j, ans, sum : longint; 10 st : string; 11 12 procedure make_trie; 13 var 14 p, x, i : longint; 15 16 begin 17 p := 1; 18 for i := 1 to len do begin 19 x := ord(st[i]) - ord(‘A‘) + 1; 20 if tr[p, x] = 0 then begin 21 inc(tot); 22 tr[p, x] := tot; 23 end; 24 if tail[p] then tail[tr[p, x]] := true; 25 p := tr[p, x]; 26 end; 27 tail[p] := true; 28 end; 29 30 procedure make_acmach; 31 var 32 h, t, i, x, x1, y : longint; 33 34 begin 35 q[1] := 1; 36 fai[1] := 0; 37 h := 1; 38 t := 1; 39 while h <= t do begin 40 x := q[h]; 41 inc(h); 42 for i := 1 to 26 do begin 43 y := tr[x, i]; 44 if y > 0 then begin 45 inc(t); 46 q[t] := y; 47 x1 := fai[x]; 48 while true do begin 49 if tr[x1, i] > 0 then begin 50 fai[y] := tr[x1, i]; 51 if tail[tr[x1, i]] then tail[tr[x, i]] := true; 52 break 53 end; 54 x1 := fai[x1]; 55 end; 56 end; 57 end; 58 end; 59 end; 60 61 procedure dp(t : longint); 62 var 63 i, j, x : longint; 64 65 begin 66 for i := 1 to tot do begin 67 if tail[i] then continue; 68 for j := 1 to 26 do begin 69 x := i; 70 while true do begin 71 if tr[x, j] > 0 then begin 72 f[t, tr[x, j]] := (f[t, tr[x, j]] + f[t - 1, i]) mod prime; 73 break; 74 end; 75 x := fai[x]; 76 end; 77 end; 78 end; 79 end; 80 81 begin 82 readln(n, m); 83 tot := 1; 84 fillchar(tail, sizeof(tail), false); 85 fillchar(tr, sizeof(tr), 0); 86 for i := 1 to 26 do tr[0, i] := 1; 87 for i := 1 to n do begin 88 readln(st); 89 len := length(st); 90 make_trie; 91 end; 92 make_acmach; 93 sum := 1; 94 for i := 1 to m do 95 sum := (sum * 26) mod prime; 96 f[0, 1] := 1; 97 for i := 1 to m do 98 dp(i); 99 for i := 1 to tot do100 if not tail[i] then ans := (ans + f[m, i]) mod prime;101 writeln((sum - ans + prime) mod prime);102 end.
BZOJ1030 [JSOI2007]文本生成器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。