题目链接:uva 1462 - Fuzzy Google Suggest
题目大意:模拟google的模糊搜索,给定给一个字符串集合,然后有n次搜索,每次有一个整数x和一个字符串,表示可以对字符串进行x次修改,包括增加、修改和删除一个字符,问修改后的字符可能是字符集中有多少个字符串的前缀。
解题思路:先建立字典树,对于每次搜索,在字典树上进行dfs,根据参数x和字符串匹配的位置进行处理,对于匹配到末尾的位置标记为2,然后对于第二次dfs,搜索每个分支上最早出现2的位置即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3000005;
const int sigma_size = 26;
struct Tire {
int sz;
int g[maxn][sigma_size];
int val[maxn], vis[maxn];
int deep, ans;
char s[15];
void init();
int idx(char ch);
void insert(char* str);
int solve(char* str, int x);
void dfs(int u, int d, int x);
void clear(int u, int flag);
}AC;
int main () {
int n, x;
char str[15];
while (scanf("%d", &n) == 1) {
AC.init();
for (int i = 0; i < n; i++) {
scanf("%s", str);
AC.insert(str);
}
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s%d", str, &x);
printf("%d\n", AC.solve(str, x));
}
}
return 0;
}
void Tire::init() {
sz = 1;
val[0] = 0;
memset(g[0], 0, sizeof(g[0]));
}
int Tire::idx (char ch) {
return ch - 'a';
}
void Tire::dfs (int u, int d, int x) {
if (x < 0)
return;
if (vis[u] == 0)
vis[u] = 1;
if (d == deep) {
vis[u] = 2;
return;
}
int v = idx(s[d]);
if (g[u][v])
dfs(g[u][v], d + 1, x);
dfs(u, d + 1, x - 1);
for (int i = 0; i < sigma_size; i++) {
if (g[u][i]) {
dfs(g[u][i], d, x - 1);
dfs(g[u][i], d + 1, x - 1);
}
}
}
void Tire::clear(int u, int flag) {
if (vis[u] == 0)
return;
if (flag && vis[u] == 2) {
ans += val[u];
flag = 0;
}
for (int i = 0; i < sigma_size; i++) {
if (g[u][i])
clear(g[u][i], flag);
}
vis[u] = 0;
}
int Tire::solve(char* str, int x) {
ans = 0;
deep = strlen(str);
strcpy(s, str);
dfs(0, 0, x);
clear(0, 1);
return ans;
}
void Tire::insert(char* str) {
int u = 0, n = strlen(str);
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
if (g[u][v] == 0) {
val[sz] = 0;
memset(g[sz], 0, sizeof(g[sz]));
g[u][v] = sz++;
}
u = g[u][v];
val[u]++;
}
}
分享到:
相关推荐
SMC-and-Fuzzy-logic-controller-for-AUV-master_slidingmodefuzzy_smc_模糊滑模_模糊滑模仿真_AUV仿真_源码.zip
Neuro-Fuzzy and Soft Computing 很经典的一本书。好不容易找到了了电子版的,与大家共享
论文研究-R-fuzzy粗糙近似隶属度集的优势测度方法及其视觉感知应用.pdf, R-fuzzy集以粗糙集的形式给出了隶属函数,按照隶属度与描述符的相关程度将其进行分类.完全符合...
scikit-fuzzy scikit-fuzzy是SciPy的模糊逻辑工具箱。 scikit-fuzzy的目标是: 为社区提供独立开发和实施的模糊逻辑算法的强大工具包 提高科学Python作为封闭源选项的有效替代方法的吸引力。 请引用 如果您发现...
为了提高对大惯性大时滞复杂受控对象的控制品质,采用基于I-Fuzzy-Smith算法的融合控制策略方法,研究了受控对象的控制难点,集成模糊、Smith预估和积分控制优势,给出了I-Fuzzy-Smith融合控制算法,构建了三种控制结构的...
clj-fuzzy, 一种处理模糊字符串和语音的算法集合 clj模糊clj模糊是一个本机Clojure库,提供了处理模糊字符串和语音的著名算法的Collection 。它可以在 Clojure 。ClojureScript 。客户端JavaScript和 Node.js. 中...
Chapter 1—Fuzzy Logic and Neuro-Fuzzy Systems in Medicine and Bio-Medical Engineering: A Historical Perspective 1. The First Period: The Infancy 2. Further Developments and Background 3. Neuro...
本源程序用于基于线性矩阵不等式的单级倒立摆T-S模糊控制,供学习研究
presents a novel adaptive neuro-fuzzy control approach for the renewable interfacing inverter. The main objective is to achieve smooth bidirectional power flow and nonlinear unbalanced load ...
c++-neural-networks-and-fuzzy-logic
razo-zapata-fuzzy-RL-wavelet-networks.zip
这是基于Neuro-Fuzzy的图像融合源码。下载解压后直接运行。
基于Delphi专家排序,对传统AHP-Fuzzy算法从问卷数据处理和比较矩阵建立两个方向进行了改进,使该算法更适合Jack虚拟环境下的人机布局评价。侧重于工作空间中操纵器的人机布局虚拟评价。为解决目前人因工程分析工具...
Ajax-Medical-diagnosis-using-fuzzy-logic.zip,一种基于web项目的软计算方法,有助于根据患者的症状预测疾病。同时告知患者附近医生的可用性和应采取的预防措施。项目的核心是模糊逻辑,这是一种利用专家(医生)...
详细给定了模糊PSO模型算法,可以用于matlab工具箱
this file includes mppt-fuzzy-pooo
首先从L-fuzzy集的层次结构出发,在L-fuzzy拓扑空间中引进了L-fuzzy子集的一种复盖,并讨论了这种复盖与L-fuzzy子集的远域族之间的关系.然后给出了良紧集、强L-fuzzy紧集、L-fuzzy紧集、L-fuzzy仿紧(L一fuzzy Ⅱ仿...
开源项目-MohamedBassem-fuzzy-dns.zip,FuzzyDNS - A simple DNS server that fuzzily matches its records
Introduction to Neuro-Fuzzy Systems 神经模糊系统
Aplicaç õ es em Engenharia de Redes Neurais Artificiais, Lógica Fuzzy e Sistemas Neuro-Fuzzy