[UVA11019] Matrix Matcher AC自动机

2023-12-07 07:08

本文主要是介绍[UVA11019] Matrix Matcher AC自动机,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本来RK在这道题快得多的....

自动机就自动机吧

Pc[i]表示编号 Next[i]表示下一个相同行 Now在全局表示当前处理到了第几行

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define SF scanf
#define PF printf
#define max(a, b) ((a) < (b) ? (b) : (a))
using namespace std;
typedef long long LL;
const int MAXN = 1000;
const int MAXL = 10000;
const int SZ = 26;
char s[MAXN+10][MAXN+10], P[MAXN/10+10][MAXN/10+10];
int ans, Now;
int Pc[MAXN+10], Next[MAXN+10], Len[MAXN+10];
int cnt[MAXN+10][MAXN+10];
struct Aho_Corasick
{int ch[MAXL+10][SZ], Ncnt, val[MAXL+10];int f[MAXL+10], last[MAXL+10];void init() { memset(ch[0], 0, sizeof(ch[0])); Ncnt = 1; }void Match(int pos, int v){int cur = Pc[v-1];int c = pos - Len[cur] + 1;while(cur >= 0) {if(Now >= cur)cnt[Now - cur][c]++;cur = Next[cur];}}void New() {memset(ch[Ncnt], 0, sizeof(ch[Ncnt]));val[Ncnt] = 0;}inline int ID(char c) { return c - 'a'; }void insert(char *s, int v){int u = 0, n = strlen(s);for(int i = 0; i < n; i++){int c = ID(s[i]);if(!ch[u][c]) {New();ch[u][c] = Ncnt++;}u = ch[u][c];}val[u] = v;}void getFail(){queue <int> q;f[0] = 0;for(int c = 0; c < SZ; c++){int u = ch[0][c];if(u) { f[u] = 0; q.push(u); last[u] = 0; }}while(!q.empty()){int r = q.front(); q.pop();for(int c = 0; c < SZ; c++){int u = ch[r][c];if(!u) { ch[r][c] = ch[f[r]][c]; continue; }q.push(u);int v = f[r];while(v && !ch[v][c]) v = f[v];f[u] = ch[v][c];last[u] = val[f[u]] ? f[u] : last[f[u]];}}}void add(int i, int j) {if(j) {Match(i, val[j]);add(i, last[j]);}}void solve(char *s) {int n = strlen(s), j = 0;for(int i = 0; i < n; i++){int c = ID(s[i]);j = ch[j][c];if(val[j]) add(i, j);else if(last[j]) add(i, last[j]);}}
}ac;
int main()
{int T; SF("%d", &T); while(T--) {int n, m, x, y;SF("%d%d", &n, &m);for(int i = 0; i < n; i++) SF("%s", s[i]);SF("%d%d", &x, &y);ac.init();for(int i = 0; i < x; i++) {SF("%s", P[i]);Len[i] = strlen(P[i]);Pc[i] = i;Next[i] = -1;for(int j = 0; j < i; j++) if(!strcmp(P[i], P[j])) {Pc[i] = j;Next[i] = Next[j];Next[j] = i;break;}if(Pc[i] == i) ac.insert(P[i], i + 1);}ac.getFail();memset(cnt, 0, sizeof(cnt));for(Now = 0; Now < n; Now++) ac.solve(s[Now]);ans = 0;for(int i = 0; i < n - x + 1; i++)for(int j = 0; j < m - y + 1; j++)if(cnt[i][j] == x) ans++;PF("%d\n", ans);}return 0;
}
/*
5
she
he
say
shr
her
yasherhs 
*/


这篇关于[UVA11019] Matrix Matcher AC自动机的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/464947

相关文章

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

POJ 1625 自动机

给出包含n个可见字符的字符集,以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串,求长为m且不包含上述p个字符串的字符串有多少个。 g++提交 int mat[108][108] ;int matn ;int N ;map<char ,int> to ;//ACconst int maxm = 108 ;const int kin

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

[论文笔记]LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale

引言 今天带来第一篇量化论文LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale笔记。 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 大语言模型已被广泛采用,但推理时需要大量的GPU内存。我们开发了一种Int8矩阵乘法的过程,用于Transformer中的前馈和注意力投影层,这可以将推理所需

正规式与有限自动机例题

答案:D 知识点: 正规式 正规集 举例 ab 字符串ab构成的集合 {ab} a|b 字符串a,b构成的集合 {a,b} a^* 由0或者多个a构成的字符串集合 {空,a,aa,aaa,aaaa····} (a|b)^* 所有字符a和b构成的串的集合 {空,a,b,ab,aab,aba,aaab····} a(a|b)^* 以a为首字符的a,b字符串的集

HDU 3037 今年暑假不AC

题目: http://acm.hdu.edu.cn/showproblem.php?pid=2037 题解: 对结束时间排序,然后进行一次遍历,寻找开始时间不小于上一个结束时间的节目。 代码: #include<stdio.h>#include<iostream>using namespace std;struct program{int start,end;}p[101

73. Set Matrix Zeros

题目: 解答: 提供了两种解题思路: 第一种,使用两个数组,分别标记每一行、每一列是否有0的存在,然后再去更新二维数组。 第二种,使用两个变量brow,bcol分别标记第0行,第0列是否存在0,然后使用每一行、每一列的第一个单元存储是否该行、该列存在0. 代码: class Solution {public:// 方法一void setZeroes(vector<vector<i

基于 AC 驱动的电容结构 GaN LED 模型开发和应用

随着芯片尺寸减小,微小尺寸GaN 基 Micro LED 显示面临着显示与驱动高密度集成的难题,传统直流(DC)驱动技术会导致结温上升,降低器件寿命。南京大学团队创新提出交流(AC)驱动的单电极 LED(SC-LED)结构【见图1】,利用隧穿结(TJ)降低器件的交流工作电压。为了深入理解该器件的工作原理,我司技术团队开发了基于 AC 驱动的物理解析模型,揭示了隧穿结降低器件工作电压的

Error: label vector and instance matrix must be double的解决方法

在使用uci下载的数据时,建模时出现这个错误的解决方法 首先现在UCI上面下载数据 然后右键另存为就行了。这样我们就从UCI里面下载到了训练数据 在matlab 点 导入数据,数据类型要记得选第二个, 如果选择最后一个table就会出现这个问题 最后附上代码 %%之前先import wine.date IMPORTED DATA 设为Numeric Matrix (数值矩