-- 这两个玩意是好久以前学习的, 现在大都忘记了, 重新回忆一遍.
对于一个字符串 S(文本串), 我们拥有几个子串 (模式串), 如何去求出这些子串在 S 中位置?
这时候就要用到 KMP 算法.
简要构成就不叙述了, 直接讲原理:
eg:
如下两个串, 上为文本串 (S), 下为模式串 (T), 我们从头开始匹配.
- S:abcabdabd
- T:abcabc
到了某一位发现不一样:
- S:abcabdabd
- T:abcabc
那么我们就将模式串右移, 因为 ab 两个字母是重复的.
- S:abcabdabd
- T: abcabc
继续匹配......
这个右移的过程是通过 next 数组实现的, 它用来确定失配后变化的位置.
求 next 数组的方式:
很简单, 不赘述了.
- void nextst()
- {
- int j=0,k=-1;
- nexts[0]=-1;
- while(j<s2.length()){
- if(k==-1||s2[j]==s2[k]){
- nexts[++j]=++k;
- }
- else k=nexts[k];
- }
- }
细心发现, 这就是个模式串自匹配.
剩下的没啥好说的. 我懒.
模板 https://www.luogu.org/problem/P3375
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+10;
- string s1;
- string s2;
- int nexts[maxn];
- void nextst()
- {
- int j=0,k=-1;
- nexts[0]=-1;
- while(j<s2.length()){
- if(k==-1||s2[j]==s2[k]){
- nexts[++j]=++k;
- }
- else k=nexts[k];
- }
- }
- void kmp(){
- int i=0,j=0;
- while(j<=s2.length()){
- if(j==s2.length()){
- cout<<i-s2.length()+1<<endl;
- j=nexts[j];
- }
- if(i>=s1.length()) break;
- while(j>=0&&s1[i]!=s2[j]) j=nexts[j];
- i++;
- j++;
- }
- }
- int main(){
- cin>>s1>>s2;
- nextst();
- kmp();
- for(int i=1;i<=s2.length();i++){
- cout<<nexts[i]<<" ";
- }
- cout<<endl;
- return 0;
- }
AC 自动机, 顾名思义, 就是可以帮助你 AC problem 的东西借用 OIWIKI 上的一句话:
AC 自动机利用一个 fail 指针来辅助多模式串的匹配.
我认为这句话基本可以概括 AC 自动机的特点和功能, 如果还有其他细节的话, 就是:
AC 自动机是 以 TRIE 的结构为基础 , 结合 KMP 的思想 建立的.
我们来看啥是 TRIE 树:
没啥好看的, 就是一棵由字符构成的树, 每个节点都是一个字符, 节点的儿子是其他字符, 大概长这样:
(网上找的图)
这张图就是 he she is hers(意义不明)
接着有个叫 fail 指针的东西, 类似于 next 数组, 也是用来找匹配的.
如何构建?
这里引用一下 OIWIKI 上讲的:
我只会写普通版的模板, 找空学一下优化:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+10;
- int n,cnt=1,rt=1;
- struct trie{
- int ch[27];
- int end;
- int next;
- }zh[maxn];
- void ins(const string &s){
- int o=rt;
- for(int i=0;i<s.length();i++){
- int &t = zh[o].ch[s[i]-'a'];
- if (!t) t = ++cnt;
- o = t;
- }
- zh[o].end++;
- }
- void failed(){
- queue<int> a;
- zh[rt].next=rt;
- a.push(rt);
- while(!a.empty()){
- int t=a.front();
- a.pop();
- for(int i=0;i<26;i++){
- if(zh[t].ch[i]){
- int fat=zh[t].next;
- while(!zh[fat].ch[i]&&fat!=rt){
- fat=zh[fat].next;
- }
- zh[zh[t].ch[i]].next=(zh[fat].ch[i]&&t!=rt)?zh[fat].ch[i]:fat;
- a.push(zh[t].ch[i]);
- }
- }
- }
- }
- int sear(const string &s){
- int o=rt,res=0;
- for(int i=0;i<s.length();i++){
- if(zh[o].ch[s[i]-'a']) o=zh[o].ch[s[i]-'a'];
- else{
- o=zh[o].next; //zh[o].next
- while(!zh[o].ch[s[i]-'a']&&o!=rt){
- o=zh[o].next;
- }
- o=(zh[o].ch[s[i]-'a'])?zh[o].ch[s[i]-'a']:o;
- }
- for(int t=o;t!=rt&&zh[t].end!=-1;t=zh[t].next){
- res+=zh[t].end;
- zh[t].end=-1;
- }
- }
- return res;
- }
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++){
- string s;
- cin>>s;
- ins(s);
- }
- failed();
- string t;
- cin>>t;
- cout<<sear(t)<<endl;
- return 0;
- }
那么回忆就暂时到此结束了, 以后会找空更新这个页面的.
来源: http://www.bubuko.com/infodetail-3166078.html