[BZOJ 1030] 텍스트 생 성기 AC 자동 동기 + DP

나 너무 못 해...모두 std 를 베 낀 후에 이해 하 는 거 야...사상 을 보충 하려 면 먼저 읽 을 수 없 는 모든 것 을 구하 고 빼 면 된다.f [i, j] 는 AC 자동 동기 에서 i 걸음 으로 j 점 에 도착 하여 단 어 를 구성 하 는 방안 수 를 나타 낸다.우선 단어 끝 에 있 는 모든 점 을 표시 해 야 합 니 다. 걸 을 수 없습니다. 그리고 fail 나 무 를 따라 단어 끝 에 있 는 점 까지 걸 을 수 없습니다. 이것 은 AC 자동 동 기 를 만 드 는 김 에 처리 해 야 합 니 다.그리고 AC 자동 동기 에 대해 작은 처 리 를 할 수 있 습 니 다. trie [i, c] = 0 (존재 하지 않 음) 이 있 으 면 trie [fail [i], c] 를 부여 하고 마지막 dp 에 서 는 fail 트 리 를 상관 하지 마 십시오.이동 은 f [i, trie [j, c] = f [i, trie [j, c]] + f [i - 1, j] 입 니 다.나 는 줄곧 어떤 나타 나 지 않 은 자모 가 어떻게 만들어 진 것 인지 잘 이해 하지 못 했 는데, 후에 모두 0 위 에 있다 는 것 을 알 게 되 었 다.
코드:

const
  maxn=6000;
  maxm=105;
  md=10007;
var
  n,m,i,tot,ans:longint;
  trie:array[0..maxn,'A'..'Z']of longint;
  fail:array[0..maxn]of longint;
  s:ansistring;
  f:array[0..maxm,0..maxn] of longint;
  place:array[-1..26*maxn]of boolean;
procedure ins(s:ansistring);
var
  i,len,p:longint;
begin
  p:=0;
  len:=length(s);
  for i:=1 to len do
  begin
    if trie[p,s[i]]=0 then begin inc(tot); trie[p,s[i]]:=tot; end;
    p:=trie[p,s[i]];
  end;
  place[p]:=true;
end;
procedure getac;
var
  i,head,tail,x:longint;
  dl:array[0..26*maxn]of longint;
  ic:char;
begin
  head:=1;
  tail:=1;
  dl[1]:=0;
  while head<=tail do
  begin
    x:=dl[head];
    for ic:='A' to 'Z' do
      if trie[x,ic]>0 then
      begin
        inc(tail);
        dl[tail]:=trie[x,ic];
        if x<>0 then fail[trie[x,ic]]:=trie[fail[x],ic];
      end
      else if x<>0 then trie[x,ic]:=trie[fail[x],ic];
    place[x]:=place[x]or place[fail[x]];
    inc(head);
  end;
end;
procedure solve;
var
  i,j,all:longint;
  ic:char;
begin
  f[0,0]:=1;
  for i:=1 to m do
    for j:=0 to tot do
      if place[j]=false then
        for ic:='A' to 'Z' do
          f[i,trie[j,ic]]:=(f[i,trie[j,ic]]+f[i-1,j])mod md;
  ans:=0;
  for i:=0 to tot do
    if place[i]=false then ans:=(ans+f[m,i])mod md;
  all:=1;
  for i:=1 to m do all:=(all*26) mod md;
  writeln((all-ans+md)mod md);
end;

begin
  tot:=0;
  fillchar(place,sizeof(place),false);
  fillchar(trie,sizeof(trie),0);
  fail[0]:=-1;
  readln(n,m);
  for i:=1 to n do
  begin
    readln(s);
    ins(s);
  end;
  getac;
  solve;
end.