UVA 11019(Matrix Matcher-vector从迭代器中取值,AC自动机匹配字符矩阵)

Problem H
Matrix Matcher
Input:
Standard Input

Output: Standard Output

Given an N * M matrix, your task is to find the number of occurences of an X * Y pattern.

Input

The first line contains a single integer t(t ≤ 15), the number of test cases.

For each case, the first line contains two integers N and M (N, M ≤ 1000). The next N lines contain M characters each.

The next line contains two integers X and Y (X, Y ≤ 100). The next X lines contain Y characters each.

Output

For each case, output a single integer in its own line, the number of occurrences.

Sample Input Output for Sample Input


2

1 1

x

1 1

y

3 3

abc

bcd

cde

2 2

bc

cd

0

2



Problem Setter: Rujia Liu, EPS

Special Thanks: Wenbin Tang

Warming: The judge input file size is about 7 MB. So please make sure that you use a fast IO function (eg.scanf()) to read input.

AC自动机,把字符串P扔入AC自动机,然后去匹配T矩阵每行字符,

每次成功匹配,就把以当前行匹配算出来的矩阵的右上角cnt++,被+x次说明匹配矩阵成功。

注意vector中的元素用(*it)

PS:由于P中单词长度一致,故不用在print循环last

PS2:有可能同一行出现2次覆盖v,因此要用vector

#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define For(i,n) for(int i=1;i=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x v[MAXNode]; // AC自动机 int f[MAXNode],last[MAXNode]; Aho_Corasick_Automata(int _siz=0):siz(_siz){MEM(ch) Rep(i,MAXNode) v[i].clear(); MEM(f) MEM(last)} void mem(int _siz=0){siz=_siz; MEM(ch) Rep(i,MAXNode) v[i].clear(); MEM(f) MEM(last) } int idx(char c){return c-'a';} void insert(char *s,int val=1) //val!=0 表示单词末尾, PS:lrj叫它单词节点 { int u=0,n=strlen(s); Rep(i,n) { int c=idx(s[i]); if (!ch[u][c]) { ++siz; MEM(ch[siz]); ch[u][c]=siz; } u=ch[u][c]; } v[u].push_back(val); } void getFail() { queue q; Rep(c,Sigma_size) { int u=ch[0][c]; if (u) q.push(u),last[u]=0; } while (!q.empty()) { int r=q.front();q.pop(); //r--c-->u Rep(c,Sigma_size) { int u=ch[r][c]; if (!u) {ch[r][c]=ch[f[r]][c]; continue;} q.push(u); f[u]=ch[f[r]][c]; last[u]=v[f[u]].size()?f[u]:last[f[u]]; } } } void print(int j,int r,int c) //打印全串中所有以j为末尾的str { for(vector::iterator it=v[j].begin();it!=v[j].end();it++) { int P_i=(*it); if (r-(P_i-1)

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:蓝桥杯 BASIC-13 数列排序
下一篇:Find Peak Element
相关文章

poj 2778 AC自动机+DP+矩阵快速幂

poj 2778 DNA Sequence AC自动机+

用C++的基本算法实现十个数排序

hdu 2896 病毒侵袭 AC自动机 基础题

poj2778之AC自动机+矩阵快速幂

hdu 4117 GRE Words (ac自动机

用有限自动机实现正则表达式的匹配

HDU 2896 病毒侵袭 ac自动机(简单)

HDU 3695 Computer Virus on Pla

SCUT 2014 B题 Numbers (DFA有穷自

图文推荐
uva 757 Gone Fis
UVA 11019(Matrix Matcher-vector从迭代器中取值,AC自动机匹配字符矩阵)
ZOJ 3640 Help Me
UVA 11019(Matrix Matcher-vector从迭代器中取值,AC自动机匹配字符矩阵)
CF 518C(Anya and
UVA 11019(Matrix Matcher-vector从迭代器中取值,AC自动机匹配字符矩阵)
hdu 1016 Prime R

分类:默认分类 时间:2012-03-17 人气:0
本文关键词:
分享到:

相关文章

  • UVa 11019 Matrix Matcher 字符矩阵出现次数 2014-02-01

    题目来源:UVa 11019 Matrix Matcher 题意:输入2个字符矩阵 求第二个字符矩阵在第一个字符矩阵中出现的次数 思路:见大白书218页 #include #include #include #include using namespace std; const int maxn = 1010; const int maxm = 110; char a[maxn][maxn]; char b[maxm][maxm]; int cnt[maxn][maxn]; int n, m,

  • UVA 11019 字符矩阵哈希 2014-05-14

    思路:以前没做过字符矩阵的哈希,所以这题是看别人博客写的。 #pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define lson i 点击复制链接 与好友分享!回本站首页 您对本文章有什么意见

  • hdu 5183-Negative and Positive (NP) 2014-10-01

    题目:大概意思就是给定一个序列a[0],a[1]....a[n-1]和一个整数k,问是否有这样的两个下标是的NP-Sum(i,j)=k,这里NP-Sum(i,j)=a[i]-a[i+1]+a[i+2]-...+(-1)^(j-1)*a[j]。 思路:我们可以维护这个序列的后缀和(前缀也是可以的),然后枚举sum[i]查看在set表中是否存在sum[j]=sum[i]-k。 这里要分成i为奇数时的计算和偶数时的计算(原因是我们只维护一次sum的值,或+-+-+的形式,或-+-+-的形式),具体看代

  • 1019. General Palindromic Number 2015-01-07

    A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers. Although palindromic numbers are most often cons

  • HDOJ 4619 Warm up 2 2012-08-08

    留下的数目 = 连通的木块的数目 - 连通的木块的数目/2..... 并查集维护即可...... Warm up 2 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1635 Accepted Submission(s): 735 Problem Description   Some 1×2 dominoes are placed on a

  • LeetCode 59 Permutation Sequence 2013-09-22

    The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation seq

  • UVA 1048 - Low Cost Air Travel(最短路) 2014-11-05

    UVA 1048 - Low Cost Air Travel 题目链接 题意:给定一些联票,在给定一些行程,要求这些行程的最小代价 思路:最短路,一张联票对应几个城市就拆成多少条边,结点表示的是当前完成形成i,在城市j的状态,这样去进行最短路,注意这题有坑点,就是城市编号可能很大,所以进行各种hash 代码: #include #include #include #include #include using namespace std; const int MAXNODE = 50005; c

  • LeetCode之Rotate Image 2014-01-23

    【题目】 You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? 【题意】 给定一个n*n个2维矩阵来表示一个图。在原矩阵上旋转图形90°。 【分析】 思路1: vcD4KPHA+QVswXVswXSAtPiBBWzBdWzNdQVsxXVswXSAtPiBBWzBdWzJdP

  • poj 3225 Help with Intervals(线段树) 2012-10-17

    题目链接:poj 3225 Help with Intervals 题目大意:模拟集合操作,输出最终的集合。 解题思路:线段树。 U l r:[l,r]区间置为1 I l r:[0,l),(r,maxn]置为0 D l r:[l,r]区间置为0 C l r:[0,l),(r,maxn]置为0,[l,r]区间取逆 S l r:[l,r]区间取逆。 然后基本水水的线段树,注意一下区间开和闭。 #include #include #include using namespace std; const

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.097 (s). 10 q(s)