lyzqs的博客 - trie
type: channel
link: https://nakuru.cn/tag/trie/
items: AC自动机学习笔记
items: [HNOI2004]L语言

AC自动机学习笔记
type: item
date: 2019-01-22T07:56:00+00:00
description: 简介AC自动机，就算没学也肯定听过这个名字，并且让人觉得可以用这个算法自动A题(学起来其实也不是很难，自己画个图啥都理解了233大佬们都总结AC自动机是trie+kmp实际上也的确挺形象的AC自动机的作用是用来匹配多个字符串的就是给出一堆单词问一个句子中出现了多少个不同单词什么的题目前置技能kmptrie核心内容插入插入字符串和trie完全一样，没什么讲的il void ins(char *s) { int u=0; for(int i=0;s[i];i++) { int v=s[i]-'0'; if(!e[u][v]) e[u][v]=++cnt; u=e[u][v]; } v[u]=1; }构造fail指针fail指针的作用是什么呢？当然是匹配失败后跳到的位置那么是如何匹配的呢？首先在一个句子中用一个指针从前往后扫一开始从根出发，一直按指针当前的字母往下走，当失配的时候跳到失配的位置这个位置使原来后缀和现在前缀有最长公共序列嘛，怎么理解呢比如lyzqsqwqwq lyzqsqaq qwqwqfail指针的作用就算让上图w和a失配时，使a跳到满足前缀和当前单词后缀有最长公共序列的位置上然后就可以匹配下一个单词了那么如何构造呢类似kmp，用到之前节点信息一遍bfs就可以了具体多看看代码就懂了233queue<int> q; il void build() { for(int i=0;i<26;i++) if(e[0][i]) fl[e[0][i]]=0,q.push(e[0][i]); while(!q.empty()) { int u=q.front();q.pop(); for(int i=0;i<26;i++) { if(e[u][i]) { fl[e[u][i]]=e[fl[u]][i]; q.push(e[u][i]); } else e[u][i]=e[fl[u]][i];//这里可以加速，方便跳转 } } }询问上面讲的很清楚了，对于一个字符串，拿一个指针扫，然后一直跳就完事了233il int qry(char *s) { int l=strlen(s); int res=0,u=0; for(int i=0;i<l;i++) { u=e[u][s[i]-'a']; for(int j=u;j&&~v[j];j=fl[j]) res+=v[j],v[j]=-1;//根据统计方法修改代码，这里每个单词只统计一次 } return res; }总结AC自动机其实多画画图就很容易理解了233⑧说了，SASAM真难学，我去学习了

[HNOI2004]L语言
type: item
date: 2019-01-16T13:22:00+00:00
description: Trie+dp#include <bits/stdc++.h> #define il inline #define Max 2000005 using namespace std; char p[Max]; int n,m,f[Max]; int e[233][27],v[233],cnt,len,ans; il void ins(char *s) { int u=0,l=strlen(s+1); len=max(len,l); for(int i=1;i<=l;i++) { int v=s[i]-'a'; if(!e[u][v]) e[u][v]=++cnt; u=e[u][v]; } //cout<<"qwq:"<<u<<endl; v[u]=1; } il bool find(int s,int t) { int u=0; for(int i=s;i<=t;i++) { int v=p[i]-'a'; if(!e[u][v]) return 0; u=e[u][v]; } return v[u]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%s",p+1); ins(p); } for(int i=1;i<=m;i++) { scanf("%s",p+1); memset(f,0,sizeof(f)); int l=strlen(p+1); ans=0;f[0]=1; for(int j=1;j<=l;j++) { for(int k=max(j-len,0);k<=j;k++) { //puts("qwq"); //cout<<k+1<<' '<<j<<' '<<find(k+1,j)<<endl; if(f[k]&&find(k+1,j)) { f[j]=1; ans=j; break; } } } cout<<ans<<endl; } }