题目链接:uva 11019 - Matrix Matcher
题目大意:给出一个n∗m的字符矩阵T,要求找出给定r∗c的字符矩阵P在T中出现的次数。
解题思路:对P矩阵中的每一行做一个字符串,形成一个字符串集合。构建AC自动机,然后对T矩阵中的每一行进行一次查找,对应出现在该字符串中的子串对应位置+1,如果有一个位置上r次匹配,那么就存在一个匹配矩阵。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1005;
const int maxl = 10005;
const int sigma_size = 127;
char s[maxn][maxn];
int N, M, R, C;
struct Aho_Corasick {
int sz;
int ac[maxl][sigma_size];
int vn[maxl], val[maxl][105];
int fail[maxl], last[maxl];
int cnt[maxn][maxn];
void init ();
int idx (char ch);
void insert (int x, char* str);
void get_fail ();
void find (int id, int c, char *str);
void count_ans(int x, int y, int u);
}ac_map;
void init () {
char word[105];
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++)
scanf("%s", s[i]);
ac_map.init();
scanf("%d%d", &R, &C);
for (int i = 1; i <= R; i++) {
scanf("%s", word);
ac_map.insert(i, word);
}
ac_map.get_fail();
}
int solve () {
for (int i = 1; i <= N; i++)
ac_map.find(i, C, s[i]);
int ret = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (ac_map.cnt[i][j] == R)
ret++;
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
printf("%d\n", solve());
}
return 0;
}
void Aho_Corasick::init () {
sz = 1;
vn[0] = 0;
memset(ac[0], 0, sizeof(ac[0]));
memset(cnt, 0, sizeof(cnt));
}
int Aho_Corasick::idx (char ch) {
return ch;
}
void Aho_Corasick::insert (int x, char* str) {
int n = strlen(str), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
if (ac[u][v] == 0) {
vn[sz] = 0;
memset(ac[sz], 0, sizeof(ac[sz]));
ac[u][v] = sz++;
}
u = ac[u][v];
}
val[u][vn[u]++] = x;
}
void Aho_Corasick::get_fail () {
fail[0] = 0;
queue<int> que;
for (int i = 0; i < sigma_size; i++) {
int u = ac[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 = 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] = vn[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void Aho_Corasick::count_ans (int x, int y, int u) {
if (u) {
for (int i = 0; i < vn[u]; i++)
if (x >= val[u][i])
cnt[x - val[u][i]][y]++;
count_ans(x, y, last[u]);
}
}
void Aho_Corasick::find(int x, int y, char* str) {
int n = strlen(str), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(str[i]);
u = ac[u][v];
if (vn[u])
count_ans(x, i - y + 1, u);
else if (last[u])
count_ans(x, i - y + 1, last[u]);
}
}
分享到:
相关推荐
前端开源库-jest-matcher-deep-close-tojest matcher deep-close,扩展jest以断言具有近似值的数组
Laravel开发-laravel-score-matcher 指定雄辩的模型
特征点匹配,Feature point matching Feature point matching
安装曲线匹配器可以通过NPM或Yarn安装yarn add curve-matcher或者npm install curve-matcher入门curve-matcher的核心是一个名为shapeSimilarity的函数,该函数估计2条曲线的形状彼此之间的相似程度,并返回介于0和1...
JAVA正则表达式--Pattern和Matcher 现在JDK1.4里终于有了自己的正则表达式API包,JAVA程序员可以免去找第三方提供的正则表达式库的周折了,我们现在就马上来了解一下这个SUN提供的迟来恩物- -对我来说确实如此。...
Hamcrest Feature Matcher Generator for POJOs Inspired by lot of dummy work to create matchers for fields in auto-generated beans to write POJO-based tests. Generates Hamcrest's Feature Matchers ...
基于GMS特征的图像匹配,C++,matlab,python
论文GMS: Grid-based Motion Statistics for Fast, Ultra-robust Feature Correspondence源代码,包括matlab实现版本和python实现版本。其中,matlab版本要有对应的dll,python版本要安装对应版本的库,否则会有报错...
GMS:基于网格的运动统计信息,可实现快速,超鲁棒的功能对应 出版物: ,,松下,杨赛洁,tanh达阮,成明明, GMS:基于网格的运动统计,用于快速,超鲁棒的特征对应, CVPR 2017 ,[] [ ] [] [] [ ] ...
Matlab集成的c代码GMS:基于网格的运动统计信息,可实现快速,超鲁棒的功能对应 出版物: ,林文彦,松下康幸,杨赛杰,阮达仁,成明明, GMS:基于网格的运动统计,可实现快速,超鲁棒的特征对应, ...
要求Python 3.6+ ANTLR Python运行时(4.7+) 3) python-dateutil( ) 六个( ) stix2-patterns( ) (用于运行测试)-pytest( )安装用安装: $ pip install stix2-matcher用法安装软件包会创建一个stix2-...
Swift和Objective-C的Matcher框架
slyn-url-matcher-factory
matcher - 简单的通配符匹配
JS_project_medieval-meme_matcher-源码.rar
yarn add data-matcher npm install data-matcher data-matcher 的使用方式 data-matcher 包含两种使用方式:组合转换、单独转换。 当元数据与目标数据的结构差异较大,需要经过多种转换器共同作用时适合使用组合...
浏览器支持IE 10以上火狐浏览器Chrome合金苹果浏览器安装npm install media-query-matcher --save例子 var MediaQueryMatcher = require ( 'media-query-matcher' ) ;var mqMatcher = new MediaQueryMatcher ( {'...
ph-web.zip,具有基本Web功能的Java库和具有通用Web素材的Java库
Pokemon-SV-Matcher 此工具用于匹配蛋 sv 和训练师 sv 以孵化出闪亮的口袋妖怪。
前端开源库-jeefo_url_matcherjeefo_url_matcher,jeefo框架的一部分