hdu 2825 Wireless Password(AC 로봇 + Sype DP)
제목 대의: N, M, K, M 문자열을 키 코드 집합으로 하고 현재 길이는 N을 요구하며 K 이상의 키 코드를 포함하는 문자열은 몇 개입니까?
문제풀이 사고방식: AC자동기+dp, 스크롤 수조, 키 코드 개수가 10개를 넘지 않기 때문에 우리는 이진수로 일치하는 상태를 표시한다.dp[i][j][k]
i번째 위치, j 노드, k개의 문자열과 일치하는 것을 나타낸다.
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 255;
const int sigma_size = 26;
const int mod = 20090717;
inline int bitcount (int x) {
return x == 0 ? 0 : bitcount(x>>1) + (x&1);
}
struct Aho_Corasick {
int sz, g[maxn][sigma_size];
int tag[maxn], fail[maxn], last[maxn];
int dp[2][maxn][1030];
void init();
int idx(char ch);
void insert(char* str, int k);
void getFail();
void match(char* str);
int put(int u);
int solve();
}AC;
int N, M, K;
int main () {
while (scanf("%d%d%d", &N, &M, &K) == 3 && N + M + K) {
char w[30];
AC.init();
for (int i = 1; i <= M; i++) {
scanf("%s", w);
AC.insert(w, i);
}
if (K > M)
printf("0
");
else
printf("%d
", AC.solve());
}
return 0;
}
int Aho_Corasick::solve() {
getFail();
memset(dp[0], 0, sizeof(dp[0]));
dp[0][0][0] = 1;
for (int x = 0; x < N; x++) {
int now = x&1;
int nxt = now^1;
memset(dp[nxt], 0, sizeof(dp[nxt]));
for (int i = 0; i < sz; i++) {
for (int k = 0; k < (1<<M); k++) {
if (dp[now][i][k] == 0)
continue;
for (int j = 0; j < sigma_size; j++) {
int u = i;
while (u && g[u][j] == 0)
u = fail[u];
u = g[u][j];
int d = tag[u];
dp[nxt][u][k|d] = (dp[nxt][u][k|d] + dp[now][i][k]) % mod;
}
}
}
}
int n = 0, v[1030];
memset(v, 0, sizeof(v));
for (int i = 0; i < (1<<M); i++)
if (bitcount(i) >= K)
v[n++] = i;
int ans = 0, d = N&1;
for (int u = 0; u < sz; u++) {
for (int i = 0; i < n; i++)
ans = (ans + dp[d][u][v[i]]) % mod;
}
return ans;
}
void Aho_Corasick::init() {
sz = 1;
tag[0] = 0;
memset(g[0], 0, sizeof(g[0]));
}
int Aho_Corasick::idx(char ch) {
return ch - 'a';
}
int Aho_Corasick::put(int u) {
return 0;
}
void Aho_Corasick::insert(char* str, int k) {
int u = 0, n = strlen(str);
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
if (g[u][v] == 0) {
tag[sz] = 0;
memset(g[sz], 0, sizeof(g[sz]));
g[u][v] = sz++;
}
u = g[u][v];
}
tag[u] = (1<<(k-1));
}
void Aho_Corasick::match(char* str) {
int n = strlen(str), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
while (u && g[u][v] == 0)
u = fail[u];
u = g[u][v];
}
}
void Aho_Corasick::getFail() {
queue<int> que;
for (int i = 0; i < sigma_size; i++) {
int u = g[0][i];
if (u) {
fail[u] = last[u] = 0;
que.push(u);
}
}
while (!que.empty()) {
int r = que.front();
que.pop();
for (int i = 0; i < sigma_size; i++) {
int u = g[r][i];
if (u == 0) {
g[r][i] = g[fail[r]][i];
continue;
}
que.push(u);
int v = fail[r];
while (v && g[v][i] == 0)
v = fail[v];
fail[u] = g[v][i];
tag[u] |= tag[fail[u]];
//last[u] = tag[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.