CF914F Substrings in a String
3264 ワード
問題面
英語の問題.
題意:一列(S)、二次操作あり:
1 i cは、(i)位置の文字を(c)に変更することを示す.2 l r tは、(s_{l},s_{l+1},cdots s_r)における(t)列の出現回数を表す.
\(|S|,q,\sum |t|\leq 10^5\).
問題解:暴力kmpマッチングは容易に考えられ,単一クエリの時間的複雑度は(O(|S|+|t|))である.発見(|t|)は小さい時にこのようにするのはとてもお得ではないので、ルート番号の分治を考えることができます.
(|t|)が小さい場合、(S)をブロック化すると、(t)は完全にブロック内にあるか、2つのブロックの間にあるかの2つのケースしかありません.
ブロック全体については、各ブロック内の文字列にSAMを作成し、変更があればマークをつけ、クエリー時にひっくり返して再構築します.修正回数は最大(n)回であるため,再構成の時間的複雑さは(O(nsqrt n))である.
ブロックについては,直接kmpでよい.
(t)が2つのブロックの間にある場合、左端点が前のブロックにあり、右端点が現在のブロックの位置にあることを考慮するだけで、直接kmpの複雑さも(O(|t|))である.
時間複雑度:(O(nsqrt n)).
コード:
英語の問題.
題意:一列(S)、二次操作あり:
1 i cは、(i)位置の文字を(c)に変更することを示す.2 l r tは、(s_{l},s_{l+1},cdots s_r)における(t)列の出現回数を表す.
\(|S|,q,\sum |t|\leq 10^5\).
問題解:暴力kmpマッチングは容易に考えられ,単一クエリの時間的複雑度は(O(|S|+|t|))である.発見(|t|)は小さい時にこのようにするのはとてもお得ではないので、ルート番号の分治を考えることができます.
(|t|)が小さい場合、(S)をブロック化すると、(t)は完全にブロック内にあるか、2つのブロックの間にあるかの2つのケースしかありません.
ブロック全体については、各ブロック内の文字列にSAMを作成し、変更があればマークをつけ、クエリー時にひっくり返して再構築します.修正回数は最大(n)回であるため,再構成の時間的複雑さは(O(nsqrt n))である.
ブロックについては,直接kmpでよい.
(t)が2つのブロックの間にある場合、左端点が前のブロックにあり、右端点が現在のブロックの位置にあることを考慮するだけで、直接kmpの複雑さも(O(|t|))である.
時間複雑度:(O(nsqrt n)).
コード:
#include
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
templateI read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int N=316;
char c[101000],t[101000],cc;
int n,m,sum,T,ln,ans,a[101000],b[101000];
int sit,X,Y,W;
struct SAM{
int p,q,las,tot,cur,cle,len[660],link[660],ch[660][26],cnt[660],buc[660],sa[660],lft,rit,v;
I clear(int x){
len[x]=link[x]=cnt[x]=0;
F(i,0,25)ch[x][i]=0;
}
I insert(int x){
cur=++tot;clear(tot);
len[cur]=len[las]+1;p=las;las=cur;cnt[cur]=1;
while(p&&!ch[p][x])ch[p][x]=cur,p=link[p];
if(!p)return link[cur]=1,void();
q=ch[p][x];if(len[p]+1==len[q])return link[cur]=q,void();
cle=++tot;clear(cle);len[cle]=len[p]+1;link[cle]=link[q];F(i,0,25)ch[cle][i]=ch[q][i];
while(p&&ch[p][x]==q)ch[p][x]=cle,p=link[p];
link[q]=link[cur]=cle;
}
I build(){
v=1;tot=las=1;clear(1);
F(i,lft,rit)insert(a[i]);
F(i,1,tot)buc[i]=0;
F(i,1,tot)buc[len[i]]++;
F(i,1,tot)buc[i]+=buc[i-1];
FOR(i,tot,1)sa[buc[len[i]]--]=i;
FOR(i,tot,2)cnt[link[sa[i]]]+=cnt[sa[i]];
}
I solve(){
if(!v)build();
re p=1,val;
F(i,1,ln){
val=t[i]-'a';
if(!ch[p][val])return;
p=ch[p][val];
}
ans+=cnt[p];
}
}s[330];
int w[101000],nt[101000],k;
I init(){
F(i,1,ln)w[i]=t[i]-'a';w[ln+1]=-1;
nt[1]=0;k=0;
F(i,2,ln){
while(k&&w[k+1]!=w[i])k=nt[k];
if(w[k+1]==w[i])k++;
nt[i]=k;
}
// F(i,1,ln)cout<>c+1;n=strlen(c+1);F(i,1,n)a[i]=c[i]-'a';
F(i,1,n)b[i]=((i-1)/N)+1;sum=b[n];
F(i,1,sum)s[i].lft=(i-1)*N+1,s[i].rit=min(i*N,n),s[i].v=0;
cin>>m;
while(m--){
cin>>sit>>X;
if(sit==1){
cin>>cc;W=cc-'a';
a[X]=W;s[b[X]].v=0;
}
else{
T++;
cin>>Y>>t+1;ln=strlen(t+1);ans=0;
init();//if(T==104){F(i,1,ln)cout<N)kmp(X,Y);
else{
F(i,b[X]+1,b[Y]-1)s[i].solve();
if(b[X]==b[Y])kmp(X,Y);
else{
kmp(X,s[b[X]].rit);kmp(s[b[Y]].lft,Y);
if(ln>1){
F(i,b[X],b[Y]-1)kmp(max(X,s[i].rit-ln+2),min(Y,s[i+1].lft+ln-2));
}
}
}
cout<