题目链接:uva 1399 - Puzzle
题目大意:给定K和N,表示有K种不同的字符,N个禁止串,求一个最长的串使得该串不包含任何禁止串为子串。如果存在循环或者不能构成的话,输出No。
解题思路:建立AC自动机,然后在AC自动机上做dp,所有单词结尾节点为禁止点。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 50005;
const int sigma_size = 26;
struct Aho_Corasick {
int sz, ac[maxn][sigma_size];
int fail[maxn], last[maxn];
void init();
int idx(char ch);
void insert(char* s);
void get_fail();
}fuck;
int K, vis[maxn], dp[maxn], jump[maxn];
int dfs (int u) {
if (vis[u])
return -1;
if (dp[u] != -1)
return dp[u];
vis[u] = 1;
int& ret = dp[u];
jump[u] = -1;
ret = 0;
for (int i = K - 1; i >= 0; i--) {
int v = fuck.ac[u][i];
if (fuck.last[v] == 0) {
int tmp = dfs(v);
if (tmp == -1)
return -1;
if (tmp + 1 > ret) {
ret = tmp + 1;
jump[u] = i;
}
}
}
vis[u] = 0;
return ret;
}
void put_ans (int u) {
while (jump[u] != -1) {
printf("%c", 'A' + jump[u]);
u = fuck.ac[u][jump[u]];
}
printf("\n");
}
int main () {
int cas, n;
char word[55];
scanf("%d", &cas);
while (cas--) {
fuck.init();
memset(vis, 0, sizeof(vis));
memset(dp, -1, sizeof(dp));
scanf("%d%d", &K, &n);
for (int i = 0; i < n; i++) {
scanf("%s", word);
fuck.insert(word);
}
fuck.get_fail();
if (dfs(0) != -1 && dp[0])
put_ans(0);
else
printf("No\n");
}
return 0;
}
void Aho_Corasick::init() {
sz = 1;
memset(ac[0], 0, sizeof(ac[0]));
}
int Aho_Corasick::idx(char ch) {
return ch - 'A';
}
void Aho_Corasick::insert(char* s) {
int n = strlen(s), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(s[i]);
if (ac[u][v] == 0) {
memset(ac[sz], 0, sizeof(ac[sz]));
last[sz] = 0;
ac[u][v] = sz++;
}
u = ac[u][v];
}
last[u] = 1;
}
void Aho_Corasick::get_fail () {
queue<int> que;
fail[0] = 0;
for (int i = 0; i < sigma_size; i++) {
int u = ac[0][i];
if (u) {
fail[u] = 0;
que.push(u);
}
}
while (!que.empty()) {
int r = que.front();
que.pop();
for (int i = 0; i < K; i++) {
int u = ac[r][i];
if (u == 0) {
ac[r][i] = ac[fail[r]][i];
continue;
}
que.push(u);
int v = fail[r];
while (v && ac[v][i] == 0)
v = fail[v];
fail[u] = ac[v][i];
last[u] |= last[fail[u]];
}
}
}
分享到:
相关推荐
Rotate-N-Puzzle问题与N-Puzzle问题类似,问题空间也具有组合爆炸性质。经证明,Rotate-N-Puzzle的任何一个初始布局都是可解的。在此结论的基础上,给出了解长度的上界。提出了一种分治算法,在算法中的每一步,采用...
Android实现拼图游戏
关于puzzle例题的原题资源,搭配文章使用更配噢 https://editor.csdn.net/md/?articleId=124139016
人工智能作业:实现一个A-star搜索算法来解决15-puzzle问题
8-puzzle 是一款老游戏,主要用于测试新的启发式 AI 技术。 该软件使用“棋盘计数”解决任何 8 拼图组合(偶数和奇数)。 偶数组合将找到以下目标: 012 345 678 奇怪的组合会找到以下目标: 123 804 765 如何...
有许多名称,例如 8-puzzle、15-puzzle、滑动瓷砖拼图等。它是一种将n瓷砖放置在n+1个格子中,留下一个空格的拼图。 必须通过将瓷砖滑入空白区域来按顺序移动瓷砖。 某些变体使用必须未打乱的图像; 这里考虑的变化...
实训阶段三第三部分 通过完成重排拼图游戏,加深对搜索策略的理解和应用: 1)学会利用广度优先搜索算法求得指定8-数码问题(3*3拼图)的最优解; 2)学会利用启发式搜索算法求解随机生成的24-数码问题(5*5拼图)。
这个谜题叫做 8-puzzle 或 9-puzzle。 如果格子是 4??这个谜题叫做 15-puzzle 或 16-puzzle。 拼图的目标是通过仅将方块滑入空白空间的移动来消除方块的混乱,从而在移动的棋子位置显示另一个空白空间。 (来自维基...
Vue 滑块校验
sport-sliding-puzzle.apk
N-Puzzle-Solver-master.zip
8-puzzle lisp的实现源代码 支持manhattan,misplaced-tiles, linear conflict heuristics
运用了二叉堆实现的优先级队列和a*寻路算法解决了8-puzzle问题。写的随意,没有注释。代码只要稍微改动变可以支持n puzzle问题求解。
06 Fifteen-Puzzle
概述是一种游戏,它由一帧随机排列的编号方块组成,其中缺少一个方块。 目标是重新排列块,使它们有序,使用尽可能少的移动。执行它被实现为最佳优先搜索。 该问题的解决方案说明了一种称为的通用人工智能方法。...
NPuzzle求解研究报告.docx
poj 3131 Cubic Eight-Puzzle.md
Laravel开发-puzzle 使用Laravel的Blade Grunt Rest服务器的简单静态站点。
此Python 3.4实现使用A *搜索算法解决曼哈顿中的N-Puzzle问题(事实证明,曼哈顿比汉明的功能强大十亿倍)作为其允许的启发式函数。 它使用heapq数据结构来模拟优先级队列。 输入格式 启动程序后,第一行必须包含...
用A*算法解决eight-puzzle问题,参考人工智能:一种现代方法