[BZOJ 1030] [JSOI 2007] 텍스트 생 성기 [AC 자동 동기] [계수 DP]
AC 자동 동기 고전 문제 형, 데이터 가 크 지 않 고 행렬 의 빠 른 속도 로 최적화 하지 않 습 니 다.
/* Footprints In The Blood Soaked Snow */
#include <cstdio>
#include <cstring>
#define cls(a, x) memset(a, x, sizeof(a))
using namespace std;
const int maxn = 6005, maxm = 105, p = 10007, maxq = 10000;
int dp[maxm][maxn], q[maxq];
struct _acm {
int son[maxn][26], fail[maxn], acmcnt;
bool flag[maxn];
void init() {
cls(son, 0); for(int i = 0; i < maxn; i++) fail[i] = flag[i] = 0;
acmcnt = 0;
}
void insert(char *s) {
int now = 0, len = strlen(s);
for(int i = 0; i < len; i++) {
int &pos = son[now][s[i] - 'A'];
if(!pos) pos = ++acmcnt;
now = pos;
}
flag[now] = 1;
}
void getfail() {
int h = 0, t = 0;
for(int i = 0; i < 26; i++) if(son[0][i]) q[t++] = son[0][i];
while(h != t) {
int u = q[h++];
for(int i = 0; i < 26; i++)
if(!son[u][i]) son[u][i] = son[fail[u]][i];
else {
fail[q[t++] = son[u][i]] = son[fail[u]][i];
flag[son[u][i]] |= flag[fail[son[u][i]]];
}
}
}
} acm;
inline int qpow(int a, int n) {
int ans = 1;
for(int t = a; n; n >>= 1, t = t * t % p) if(n & 1) ans = ans * t % p;
return ans;
}
char str[maxm];
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%s", str);
acm.insert(str);
}
acm.getfail();
dp[0][0] = 1;
for(int i = 1; i <= m; i++) for(int j = 0; j <= acm.acmcnt; j++) for(int k = 0; k < 26; k++)
if(!acm.flag[acm.son[j][k]]) dp[i][acm.son[j][k]] = (dp[i][acm.son[j][k]] + dp[i - 1][j]) % p;
int ans = qpow(26, m);
for(int i = 0; i <= acm.acmcnt; i++) ans = (ans - dp[m][i] + p) % p;
printf("%d
", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[AC 자동 동기] hdoj 3065: 바이러스 침입 지속 중대체로 제목: n 개의 패턴 문자열, 하나의 텍스트 문자열 을 보 여 줍 니 다. 각각 텍스트 문자열 이 패턴 문자열 에 나타 나 는 횟수 를 구 합 니 다. 대체적인 사고방식: 기본 적 인 AC 자동 동 기 는 일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.