BZOJ1030 JSOI 2007 텍스트 생성기 문제풀이 & 코드

제목: n개의 일치 문자열을 제시하고, 질문: 길이가 m인 문자열에 대해 몇 개의 문자열이 최소한 일치 문자열(답은 10007에 대한 모형을 취함)을 포함하는 문제풀이를 포함한다.'최소한 일치 문자열의 길이가 m인 문자열을 포함한다'. 그러면'모든 문자열은 어떤 일치 문자열이 포함되지 않은 길이가 m인 문자열을 제외한다'로 쉽게 전환된다. 그 다음은 즐겨 보는 AC자동기의 dp이다.dp방정식은 분명히 dp[i][j]가 길이가 i인 꼬리가 j위에 일치할 때 얼마나 많은 꼬리가 포함되지 않는지 나타낸다. dp[i][ch[j][k]]]+=dp[i-1][j]즉 아이 노드는 반드시 유효한 아버지 노드가 추측한다(노드 자체flag지침이true인 것은 당연히 0)

/**************************************************************
 Problem: 1030
 User: Rainbow6174
 Language: C++
 Result: Accepted
 Time:76 ms
 Memory:4396 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#define MOD 10007
using namespace std;
const int maxt = 6005;
int n, m, tot, ans = 1, temp, ch[maxt][26], fail[maxt], q[maxt], dp[105][maxt];
char s[105];
bool flag[maxt];
void newnode(int x, int v)
{
 ch[x][v]=++tot;
}
void addtrie(char s[])
{
 int x = 0, p = 0, len = strlen(s);
 while( p < len )
 {
 temp = s[p]-'A';
 if ( !ch[x][temp] ) newnode(x, temp);
 x = ch[x][temp];
 p++;
 }
 flag[x] = 1;
}
void AC(void)
{
 int h = 0, t = 0;
 for(int i = 0; i < 26; i++)
 if(ch[0][i]) q[t++] = ch[0][i];
 while( h < t )
 {
 temp = q[h++];
 for(int i = 0; i < 26; i++)
 if( !ch[temp][i] ) ch[temp][i] = ch[fail[temp]][i];
 else fail[ch[temp][i]] = ch[fail[temp]][i],
 flag[ch[temp][i]] |= flag[fail[ch[temp][i]]],
 q[t++] = ch[temp][i];
 }
}
int main(void)
{
 scanf("%d%d", &n, &m);
 for(int i = 0; i < n; i++)
 {
 scanf("%s", s);
 addtrie(s);
 }
 AC();
 dp[0][0] = 1;
 for(int i = 1; i <= m; i++)
 {
 for(int j = 0; j <= tot; j++)
 {
 if(flag[j] || !dp[i-1][j]) continue;
 for(int k = 0; k < 26; k++)
 {
 dp[i][ch[j][k]] += dp[i-1][j];
 dp[i][ch[j][k]] %= MOD;
 }
 }
 ans*=26;
 ans%=MOD;
 }
 //cout<<ans<<endl;
 for(int i = 0; i <= tot; i++)
 {
 //cout<<i<<' '<<flag[i]<<endl;
 if(!flag[i])
 {
 //cout<<dp[m][i]<<endl;
 ans -= dp[m][i];
 ans += MOD;
 ans %= MOD;
 }
 }
 printf("%d
",ans);
 return 0;
}