首页 > 其他分享 >后缀自动机

后缀自动机

时间:2024-04-23 10:14:29浏览次数:22  
标签:dian node ch fa 后缀 len int 自动机

存储子串的出现次数
怎么把这个子串打印出来呢?

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int tot=1,las=1;
struct NODE
{
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=fa=0;}
}dian[2000010];
struct Edge
{
    int t,nexty;
}edge[2000010];
int head[2000010],cnt=0;
void jia(int a,int b)
{
    cnt++;
    edge[cnt].t=b;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
long long zhi[2000010];//存储子串出现次数 
inline void add(int c)
{
    register int p=las,np=las=++tot;zhi[tot]=1;
    dian[np].len=dian[p].len+1;
    for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;
    if(!p)dian[np].fa=1;
    else
    {
        register int q=dian[p].ch[c];
        if(dian[q].len==dian[p].len+1)dian[np].fa=q;
        else
        {
            register int nq=++tot;
            dian[nq]=dian[q];dian[nq].len=dian[p].len+1;
            dian[q].fa=dian[np].fa=nq;
            for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq;
        }
    }
}
char s[2000010];
int cd;
long long ans=0;
void dfs(int node)//这个位置在遍历所有子串的出现次数 
{
    for(register int i=head[node];i;i=edge[i].nexty)
    {
        dfs(edge[i].t);
        zhi[node]+=zhi[edge[i].t];
    }
    
	// zhi[node]是子串出现次数 
	// dian[node].len  是子串长度 
    //if(zhi[node]!=1)ans=max(ans,zhi[node]*dian[node].len);//本题是一种计算 
}
int main()
{
    scanf("%s",s);cd=strlen(s);
    for(register int i=0;i<cd;i++)add(s[i]-'a');
    for(register int i=2;i<=tot;i++)jia(dian[i].fa,i);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}

标签:dian,node,ch,fa,后缀,len,int,自动机
From: https://www.cnblogs.com/yzzyang/p/18152206

相关文章

  • 《自动机理论、语言和计算导论》阅读笔记:p261-p314
    《自动机理论、语言和计算导论》学习第10天,p261-p314总结,总计48页。一、技术总结1.generating&reachable2.ChomskyNormalForm(CNF)乔姆斯基范式。3.pumpinglemma泵作用引理。引理:引理是数学中为了取得某个更好的结论而作为步骤的已证明命题,其意义并不在于自身已完......
  • 回文自动机
    求以每个节点结尾的,回文子串的个数,最大回文子串的长度求回文串的总个数(必须连续)不连续的是动态规划#include<bits/stdc++.h>usingnamespacestd;constintmaxn=500005;charstr[maxn];structPAM{intsize,last,r0,r1;inttrie[maxn][26],fail[maxn],l......
  • AC自动机
    二次加强版那个题距离最大内存,就差了一个ss数组了....96分#include<bits/stdc++.h>#definemaxn2000001usingnamespacestd;stringss[100000];chars[maxn],T[maxn];intn,cnt,vis[200051],ans,in[maxn],Map[maxn];structkkk{intson[26],fail,flag,ans;voi......
  • js 小写转换,取后缀
    varstrfileExt=tmpFinanceReportFileName.substr(tmpFinanceReportFileName.lastIndexOf(".")).toLowerCase();    if(strfileExt!==".xls"&&strfileExt!=".xlsx"){      alertMsg.error('文件格式只能为Excel文件!&#......
  • 【学习笔记】 字符串基础 : 后缀自动机(基础篇)
    本文只介绍关于\(\mathbf{SAM}\)的基本概念与实现后缀自动机是什么类似\(\text{AC}\)自动机,后缀自动机(\(\text{SAM}\))是能且只能接收字符串所有后缀的自动机我们首先要知道,\(\mathbf{SAM}\)是只能接收所有后缀的结构而不是只能维护后缀的结构事实上\(\mathbf{SAM}\)......
  • 栈4-后缀表达式
    栈4-后缀表达式中缀转后缀数字:直接输出左括号: 进栈运算符号:与栈顶符号进行优先级比较栈顶若是左括号,优先级最低栈顶符号优先级低: 此符号进栈栈顶符号优先级不低,弹出栈顶符号后进栈右括号:将栈顶符号弹出并输出,知道匹配到左括号遍历结束:弹出并输出所......
  • 栈5-后缀表达式求解
    栈5-后缀表达式的求解求解过程831-5*+数字:进栈[1,3,8]符号:-从栈中弹出右操作数-1从栈中弹出左操作数3-1根据符号进行运算2将运算结果压入栈中[2,8]遍历结束,栈中唯一的数字作为计算结果定义栈结构typedefstructMYNUM{LinkNodenode;int......
  • 后缀数组学习笔记
    定义后缀数组是什么?(下文用\(Suf_S[i]\)表示\(S[i,i+1,\cdots,|S|]\),对\(Suf_T\)同理。并用\(S[l,r]\)表示\(S[l,l+1,\cdots,r]\),对\(T[l,r]\)同理)后缀数组包含两个数组\(rk,sa\)。\(rk[i]\)表示后缀\(Suf_S[i]\)排序后的排名。\(sa[i]\)表示排......
  • 后缀数组学习笔记
    定义后缀从字符串某个位置i到字符串末尾的子串,定义s的第i个字符为第一个元素的后缀为suf(i)。后缀数组把s的每一个后缀按照字典序排序,后缀数组sa[i]表示排名为i的后缀的起始位置的下标。rk[i]数组代表起始位置为i的后缀的排名。rk[]和sa[]是一一对应关系,互为逆运算,可以相互......
  • 后缀数组 学习笔记
    理论知识详见OIWiki。模板后缀排序一切有关后缀数组问题的必备板子。求后缀数组模板题,OIWiki有详解。点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'#definesortstable_sortusingnamespacestd;constintN=1e6+10;template......