NC20972. [NOI2018]你的名字
描述
输入描述
第一行一个字符串 S ，之后询问给出的 ION2017 的命名串都是 S 的连续子串。
第二行一个正整数 Q，表示询问次数。
接下来 Q 行，每行有一个字符串 T 和两个正整数 l,r，表示询问如果 ION2017 的
命名串是 S [l..r]，ION2018 的命名串是 T 的话，有几种命名方式一定满足规定。
保证输入中给出的字符串都是由小写字母构成的。
输出描述
输出 Q 行，第 i 行一个非负整数表示第 i 个询问的答案
示例1
输入:
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
输出:
12 10 4
C++14(g++5.4) 解法, 执行用时: 1408ms, 内存消耗: 342352K, 提交时间: 2018-12-21 19:05:11
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=500005;
namespace Tree {
#define ls lc[x]
#define rs rc[x]
#define mid ((l+r)>>1)
int lc[maxn*40],rc[maxn*40],cnt;
inline void Insert(int &x,int l,int r,int p) {
if(!x)
x=++cnt;
if(l==r)
return;
if(p<=mid)
Insert(ls,l,mid,p);
else
Insert(rs,mid+1,r,p);
}
inline int Merge(int a,int b) {
if(!a||!b)
return a|b;
int x=++cnt;
ls=Merge(lc[a],lc[b]),rs=Merge(rc[a],rc[b]);
return x;
}
inline int Query(int x,int l,int r,int ql,int qr) {
if(!x||ql>qr)
return 0;
if(ql<=l&&r<=qr)
return 1;
if(ql<=mid&&Query(ls,l,mid,ql,qr))
return 1;
if(qr>mid&&Query(rs,mid+1,r,ql,qr))
return 1;
return 0;
}
}
int n,q,lx,rx,rt[maxn<<1],tot[maxn<<1],sz[maxn<<1],sa[maxn<<1],lim[maxn<<1];
struct SAM {
struct Node {
int fa,len,tag,ch[26];
inline void Clear() {
fa=len=tag=0,memset(ch,0,sizeof ch);
}
}T[maxn<<1];
int lst,cnt;
inline void Clear() {
T[lst=cnt=1].Clear();
}
inline int NewNode() {
T[++cnt].Clear();
return cnt;
}
inline void Insert(int c,int id=0) {
int p=lst,np=NewNode();
lst=np,T[np].len=T[p].len+1,sz[np]=1;
if(id)
T[np].tag=id;
for(;p&&!T[p].ch[c];p=T[p].fa)
T[p].ch[c]=np;
if(!p)
T[np].fa=1;
else {
int q=T[p].ch[c];
if(T[q].len==T[p].len+1)
T[np].fa=q;
else {
int nq=NewNode();
T[nq]=T[q],T[nq].len=T[p].len+1,T[q].fa=T[np].fa=nq;
for(;p&&T[p].ch[c]==q;p=T[p].fa)
T[p].ch[c]=nq;
}
}
}
inline void Build() {
for(int i=1;i<=cnt;++i)
tot[T[i].len]++;
for(int i=1;i<=n;++i)
tot[i]+=tot[i-1];
for(int i=cnt;i;--i)
sa[tot[T[i].len]--]=i;
for(int i=cnt;i;--i) {
int p=sa[i];
if(sz[p])
Tree::Insert(rt[p],1,n,T[p].len);
rt[T[p].fa]=Tree::Merge(rt[T[p].fa],rt[p]);
}
}
inline ll Calc() {
ll res=0;
for(int i=2;i<=cnt;++i)
res+=max(0,T[i].len-max(lim[T[i].tag],T[T[i].fa].len));
return res;
}
}Sam1,Sam2;
char s[maxn],t[maxn];
int main() {
scanf("%s",s+1);
n=strlen(s+1);
Sam1.Clear();
for(int i=1;i<=n;++i)
Sam1.Insert(s[i]-'a');
Sam1.Build();
for(read(q);q--;) {
scanf("%s",t+1),read(lx),read(rx);
Sam2.Clear();
for(int i=1,len=0,u=1,m=strlen(t+1);i<=m;++i) {
int c=t[i]-'a';
Sam2.Insert(c,i);
for(;;) {
if(Sam1.T[u].ch[c]&&Tree::Query(rt[Sam1.T[u].ch[c]],1,n,lx+len,rx)) {
++len,u=Sam1.T[u].ch[c];
break;
}
if(!len)
break;
if((--len)==Sam1.T[Sam1.T[u].fa].len)
u=Sam1.T[u].fa;
}
lim[i]=len;
}
printf("%lld\n",Sam2.Calc());
}
}
C++ 解法, 执行用时: 1507ms, 内存消耗: 452392K, 提交时间: 2021-07-13 22:22:37
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10+2e5+10;
const int N = 1e6*22;
//下面是线段树
int sum[N],rt[maxn],ls[N],rs[N],Line,n;
void push_up(int r)
{
sum[r] = sum[ls[r]] + sum[rs[r]];
}
void add(int &root,int l,int r,int index)
{
if( l>index || r<index ) return;
if( !root ) root = ++Line;
if( l==r&&l==index ){ sum[root]=1; return; }
int mid = l+r>>1;
add( ls[root],l,mid,index); add( rs[root],mid+1,r,index );
push_up( root );
}
int ask(int &root,int l,int r,int L,int R)
{
if( l>R || r<L ) return 0;
if( root==0 ) return 0;
if( l>=L&&r<=R ) return sum[root];
int mid = l+r>>1;
return ask( ls[root],l,mid,L,R)+ask( rs[root],mid+1,r,L,R );
}
int merge(int x,int y,int l,int r)
{
if( !x || !y ) return x|y;
int p = ++Line;
if( l==r ){ sum[p]=sum[x] | sum[y]; return p; }
int mid = l+r>>1;
ls[p] = merge( ls[x],ls[y],l,mid );
rs[p] = merge( rs[x],rs[y],mid+1,r );
push_up( p );
return p;
}
char a[maxn];
int res[maxn];
struct SAM
{
int zi[maxn][27],fa[maxn],l[maxn],mi[maxn],las = 1, id = 1;
void insert(int c,int ok)
{
int p = las, np = ++id; las = id;
mi[np] = l[np] = l[p]+1;
if( ok ) add( rt[np],1,n,l[np] );
for( ;p&&zi[p][c]==0;p=fa[p] ) zi[p][c] = np;
if( !p ) fa[np] = 1;
else
{
int q = zi[p][c];
if( l[q] == l[p]+1 ) fa[np] = q;
else
{
int nq=++id;
memcpy( zi[nq],zi[q],sizeof zi[nq] );
l[nq] = l[p]+1, fa[nq] = fa[q]; mi[nq] = mi[q];
fa[np] = fa[q] = nq;
for( ;p&&zi[p][c]==q;p=fa[p] ) zi[p][c] = nq;
}
}
}
long long solve()
{
long long ans = 0;
for(int i=1;i<=id;i++) ans += max( 0,l[i]-max( l[fa[i]],res[mi[i]] ) );
return ans;
}
void init()
{
for(int i=1;i<=id;i++)
{
memset( zi[i],0,sizeof zi[i] );
fa[i] = l[i] = mi[i] = 0;
}
las = id = 1;
}
}s1,s2;
vector<int>vec[maxn];
void dfs(int u,int father)//树上倍增
{
for(auto v:vec[u] )
{
dfs( v,u );
rt[u] = merge( rt[u],rt[v],1,n );
}
}
void build()
{
scanf("%s",a+1 ); n = strlen( a+1 );
for(int i=1;i<=n;i++) s1.insert( a[i]-'a',1 );
for(int i=2;i<=s1.id;i++) vec[s1.fa[i]].push_back( i );
dfs(1,0);//线段树合并
}
int main()
{
build();
int q; scanf("%d",&q);
while( q-- )
{
int L,R,p=1;
scanf("%s%d%d",a+1,&L,&R ); int le = strlen( a+1 );
for(int i=1;i<=le;i++)
{
res[i] = res[i-1];
while( 1 )//一直去匹配即可
{
int v = s1.zi[p][a[i]-'a'];
if( v&&ask( rt[v],1,n,L+res[i],R) ) { p = v; res[i]++; break; }
if( !res[i] ) { p=1 ; break; }
res[i]--;
if( res[i]==s1.l[s1.fa[p]] ) p = s1.fa[p];
}
s2.insert( a[i]-'a',0 );
}
printf("%lld\n",s2.solve() );
s2.init();
}
}