Pty的字符串(string)
2024-08-23 01:46:40
题目描述
在神秘的东方有一棵奇葩的树,它有一个固定的根节点(编号为1)。树的每条边上都是一个字符,字符为a,b,c中的一个,你可以从树上的任意一个点出发,然后沿着远离根的边往下行走,在任意一个节点停止,将你经过的边的字符依次写下来,就能得到一个字符串,例如:
在这棵树中我们能够得到的字符串是:
c, cb, ca, a, b, a
现在pty得到了一棵树和一个字符串S。如果S的一个子串[l,r]和树上某条路径所得到的字符串完全相同,则我们称这个子串和该路径匹配。现在pty想知道,S的所有子串和树上的所有路径的匹配总数是多少?
输入格式
第一行:n
接下来n-1行,每行一个整数fa, 一个字符c,字符和整数之间用一个空格隔开
第i行fa代表第i号节点的父亲,c表示第i号节点和fa的连边的字符
最后一行为字符串S
输出格式
输出共一行,表示匹配总数,因为评测系统暂未确定,所以C/C++选手请使用cout输出。
样例
样例输入
5
1 c
2 b
1 a
2 a
cba
样例输出
5
数据范围与提示
【样例说明】
单个字符匹配的对数为4对,两个字符匹配的对数为1对:cb
solution
广义后缀自动机
其实是在trie树上建。
具体看
记录 val[i] 表示i这个状态所代表的所有串的出现次数和
val=(max-min)*right
记sum为i到根的val之和。
做匹配的时候,我们考虑新加入一个字符。
假设这个字符的匹配点是i,之前匹配长度为len。
那么这个字符的答案就是(len-s[fa].max)*ri[i]+s[fa].sum.
也就是该字符串在这个点的匹配长度,加上父亲点的sum,也就是以这个字符结尾的其他后缀的贡献。
格式化代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 800005
#define ll long long
using namespace std;
int n,id[maxn],rt=,cnt=,la=,a[maxn];
struct node{
int nex[],par,Max,ri;
ll val,sum;
}s[maxn*];
char ch[maxn*];
ll tax[maxn];
void ins(int fa,int c,int i){ int np=++cnt,p=id[fa];s[np].ri=;
//cout<<i<<' '<<c<<' '<<p<<endl;
s[np].Max=s[la].Max+;id[i]=la=np;//这里还不是很懂为什么是la for(;p&&!s[p].nex[c];p=s[p].par)s[p].nex[c]=np;
if(!p)s[np].par=rt;
else {
int q=s[p].nex[c];
if(s[q].Max==s[p].Max+)s[np].par=q;
else {
int nq=++cnt;
for(int i=;i<;i++)s[nq].nex[i]=s[q].nex[i];
s[nq].par=s[q].par;s[nq].Max=s[p].Max+;
s[q].par=s[np].par=nq;
for(;s[p].nex[c]==q;p=s[p].par)s[p].nex[c]=nq;
}
}
}
void Calc(){
for(int i=;i<=cnt;i++)tax[s[i].Max]++;
for(int i=;i<=cnt;i++)tax[i]+=tax[i-];
for(int i=;i<=cnt;i++)a[tax[s[i].Max]--]=i;
for(int i=cnt;i>=;i--){
int k=a[i],f=s[k].par;
s[f].ri+=s[k].ri;
s[k].val=s[k].ri*(s[k].Max-s[f].Max);
}
for(int i=;i<=cnt;i++){
int k=a[i];
s[k].sum=s[k].val+s[s[k].par].sum;
}
}
int main(){
cin>>n;id[]=;
for(int i=,fa;i<=n;i++){
char c;scanf("%d %c",&fa,&c);
ins(fa,c-'a',i);
}
Calc();
scanf("%s",ch);int l=strlen(ch),len=;
int p=rt;ll ans=;
for(int i=;i<l;i++){
for(;!s[p].nex[ch[i]-'a']&&p;p=s[p].par,len=s[p].Max);
if(!p)p=rt,len=;
else {
p=s[p].nex[ch[i]-'a'];len++;
int f=s[p].par;
ans=ans+s[f].sum+(len-s[f].Max)*s[p].ri;
}
}
cout<<ans<<endl;
return ;
}
最新文章
- WinObjc - 使用iOS项目生成通用Windows应用
- jmeter随笔(9)--有两种编码风格,导致数据乱码
- [转]T4模版引擎之生成数据库实体类
- 【JAVA】在编译期可直接替换的final变量
- Android学习(一)
- 如何将XML转换成XSD(XML Schema)文件
- Bootstrap 静态分页 和 jquery_pagination插件 动态分页
- zend支持sql server
- 房费制 之 登录BUG
- C# 中参数验证方式
- java获取程序执行时间
- html base2
- Google Dremel数据模型详解(下)
- Redis缓存穿透、缓存雪崩和缓存击穿理解
- Ubuntu通过ADB连接手机
- Java软件工程师面试常见问题集锦之一
- Django目录
- 小问题填坑,关于obj.x和obj[";x";]
- JSONObject的toBean 和 fromObject
- mysql 索引 create_time 加explain关键字是否走索引