BZOJ1030 [JSOI2007]文本生成器

浏览数：35 / 时间：2015年06月09日

搬运以前的题解中：

此题一看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 do
100     if not tail[i] then ans := (ans + f[m, i]) mod prime;
101   writeln((sum - ans + prime) mod prime);
102 end.