問題の概要
文字列 s と m 個のテキスト文字列 t₁, t₂, ..., tₘ が与えられる。q 回のクエリがあり、各クエリでは st, ed, ql, qr のパラメータが指定される。このとき、tₛₜ から tₑₐ の範囲内で部分文字列 s[ql,qr] が最も多く出現するテキスト文字列の番号とその出現回数を答える必要がある。前提知識
- 一般化接尾辞オートマトン（GSAM）
- 動的ノード生成セグメント木 + セグメント木のマージ
解法の考察
m 個の文字列に対して GSAM を構築する。各ノードについてカウント情報を管理する。具体的には count[i][id] をノード i における文字列 id 上の endpos のサイズとして維持する。
類似問題 P3181 を参考にすると、count[i][1] と count[i][2] を使用してそれぞれの文字列上のカウントを維持し、単一文字列 SAM と同様に parent tree 上でサブツリーの合計を計算する。最終的な答えは Σ count[i][1] × count[i][2] × (len[i] - len[link[i]]) となる。
コードを見る
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define input input()
#define newline puts("")
inline int input
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void output(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) output(x/10);
putchar(x%10+'0');
return;
}
const int MAXN = 5e5+10;
char base[MAXN];
ll count[MAXN<<1][3];
vector<int> children[MAXN<<1];
ll result;
struct GeneralizedSuffixAutomaton{
int total_nodes;int current_last;
int parent_link[MAXN<<1], length[MAXN<<1];
int transition[MAXN<<1][27];
void add_char(int c,int id)
{
int prev=current_last;
if(transition[prev][c]){
int next=transition[prev][c];
if(length[prev]+1==length[next]){
count[next][id]=1;
current_last=next;return;
}
else{
int duplicate=++total_nodes;
length[duplicate]=length[prev]+1;
parent_link[duplicate]=parent_link[next];
for(int i=1;i<=26;i++) transition[duplicate][i]=transition[next][i];
while(prev!=-1&&transition[prev][c]==next){
transition[prev][c]=duplicate;
prev=parent_link[prev];
}
parent_link[next]=duplicate;
count[duplicate][id]=1;
current_last=duplicate;
return;
}
}
int new_node=++total_nodes;
length[new_node]=length[prev]+1;
while(prev!=-1&&!transition[prev][c]){
transition[prev][c]=new_node;
prev=parent_link[prev];
}
if(prev==-1) parent_link[new_node]=0;
else{
int next=transition[prev][c];
if(length[prev]+1==length[next]) parent_link[new_node]=next;
else{
int duplicate=++total_nodes;
length[duplicate]=length[prev]+1;
parent_link[duplicate]=parent_link[next];
for(int i=1;i<=26;i++) transition[duplicate][i]=transition[next][i];
while(prev!=-1&&transition[prev][c]==next){
transition[prev][c]=duplicate;
prev=parent_link[prev];
}
parent_link[new_node]=parent_link[next]=duplicate;
}
}
count[new_node][id]=1;
current_last=new_node;
return;
}
void build_parent_tree()
{
for(int i=1;i<=total_nodes;i++){
children[parent_link[i]].push_back(i);
}
}
void calculate_subtree_counts(int node){
for(int child:children[node]){
calculate_subtree_counts(child);
count[node][1]+=count[child][1];
count[node][2]+=count[child][2];
}
}
void compute_result(){
for(int i=1;i<=total_nodes;i++)
result+=count[i][1]*count[i][2]*(length[i]-length[parent_link[i]]);
output(result);
}
}automaton;
signed main()
{
automaton.parent_link[0]=-1;
scanf(" %s",base+1);int size=strlen(base+1);
for(int i=1;i<=size;++i) automaton.add_char(base[i]-'a'+1,1);
automaton.current_last=0;
scanf(" %s",base+1);size=strlen(base+1);
for(int i=1;i<=size;++i) automaton.add_char(base[i]-'a'+1,2);
automaton.build_parent_tree();
automaton.calculate_subtree_counts(0);
automaton.compute_result();
return 0;
}
この問題に戻ると、5×10⁴個の文字列があるため、前述のように二次元配列 count を使用することは時間と空間の制約上不可能である。そのため、count 情報を動的ノード生成セグメント木に移し、セグメント木のマージ操作で維持することを考える。
具体的には、まずテキスト文字列群の GSAM を構築し、各ノード（明確に同値クラスに対応）に対して [1,m] の範囲を持つセグメント木を生成する。その後、基底文字列を追加し、各位置に対応するノードを記録する。これはクエリ処理を容易にするためである。次に parent tree を走査し、サブツリーのマージを行う（これはサブツリーの合計計算に相当）。前処理完了後にクエリ処理を開始する。s[ql,qr] に対応する同値クラスを特定するために qr からダブリングで上昇する。最後に該当ノードの [st,ed] 範囲での最大値を取得する。
ACコード
#include<bits/stdc++.h>
using namespace std;
#define input input()
#define newline puts("")
inline int input
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void output(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) output(x/10);
putchar(x%10+'0');
return;
}
const int MAXN = 5e5+10;
const int MAXM = 5e4+10;
#define NODE_LIMIT (MAXN+MAXM)<<1
char base[MAXN],text[MAXM];
int text_count;
int base_length;
int current_pos;
int position[NODE_LIMIT];
int ancestor[NODE_LIMIT][21], depth[NODE_LIMIT];
vector<int> children[NODE_LIMIT];
int root[NODE_LIMIT];
struct MaxInfo{
int value,idx;
MaxInfo(int Val=0,int Idx=0){value=Val,idx=Idx;}
bool operator > (const MaxInfo &other)const{
return value==other.value?(idx<other.idx):(value>other.value);
}
};
MaxInfo get_maximum(MaxInfo a,MaxInfo b){
if(a.value==b.value) return (a.idx<b.idx?a:b);
return (a.value>b.value?a:b);
}
namespace SegmentTree{
int node_counter;
struct Node{
int left,right;
MaxInfo answer;
#define left_child(i) nodes[i].left
#define right_child(i) nodes[i].right
#define node_answer(i) nodes[i].answer
}nodes[NODE_LIMIT<<1];
void update_node(int i){
node_answer(i)=get_maximum(node_answer(left_child(i)),node_answer(right_child(i)));
}
void insert_value(int &i,int l,int r,int x)
{
if(!i) i=++node_counter;
if(l==r){
++node_answer(i).value;
node_answer(i).idx=l;
return;
}
int mid=(l+r)>>1;
if(x<=mid) insert_value(left_child(i),l,mid,x);
else insert_value(right_child(i),mid+1,r,x);
update_node(i);
return;
}
int combine_trees(int x,int y,int l,int r){
if(!x||!y) return x+y;
int merged=++node_counter;
if(l==r){
nodes[merged]=nodes[x];
node_answer(merged).value=node_answer(x).value+node_answer(y).value;
return merged;
}
int mid=(l+r)>>1;
left_child(merged)=combine_trees(left_child(x),left_child(y),l,mid);
right_child(merged)=combine_trees(right_child(x),right_child(y),mid+1,r);
update_node(merged);
return merged;
}
MaxInfo query_range(int i,int ql,int qr,int l,int r){
if(!i) return MaxInfo(0,MAXM+1);
if(ql<=l&&r<=qr) return node_answer(i);
int mid=(l+r)>>1;
MaxInfo result(0,MAXM+1);
if(ql<=mid) result=get_maximum(result,query_range(left_child(i),ql,qr,l,mid));
if(qr>mid) result=get_maximum(result,query_range(right_child(i),ql,qr,mid+1,r));
return result;
}
}using namespace SegmentTree;
void dfs_traversal(int x){
for(int j=1;(1<<j)<=depth[x];j++)
ancestor[x][j]=ancestor[ancestor[x][j-1]][j-1];
for(int child:children[x]){
depth[child]=depth[x]+1;
ancestor[child][0]=x;
dfs_traversal(child);
root[x]=combine_trees(root[x],root[child],1,text_count);
}
}
struct GeneralizedSuffixAutomaton{
int total_nodes;
int parent_link[NODE_LIMIT], length[NODE_LIMIT];
int transition[NODE_LIMIT][27];
int add_character(int c,int id)
{
int prev=current_pos;
if(transition[prev][c]){
int next=transition[prev][c];
if(length[prev]+1==length[next]){
if(id) insert_value(root[next],1,text_count,id);
return next;
}
else{
int duplicate=++total_nodes;
length[duplicate]=length[prev]+1;
parent_link[duplicate]=parent_link[next];
for(int i=1;i<=26;i++) transition[duplicate][i]=transition[next][i];
while(prev!=-1&&transition[prev][c]==next){
transition[prev][c]=duplicate;
prev=parent_link[prev];
}
parent_link[next]=duplicate;
if(id) insert_value(root[duplicate],1,text_count,id);
return duplicate;
}
}
int new_node=++total_nodes;
length[new_node]=length[prev]+1;
while(prev!=-1&&!transition[prev][c]){
transition[prev][c]=new_node;
prev=parent_link[prev];
}
if(prev==-1) parent_link[new_node]=0;
else{
int next=transition[prev][c];
if(length[prev]+1==length[next]) parent_link[new_node]=next;
else{
int duplicate=++total_nodes;
length[duplicate]=length[prev]+1;
parent_link[duplicate]=parent_link[next];
for(int i=1;i<=26;i++) transition[duplicate][i]=transition[next][i];
while(prev!=-1&&transition[prev][c]==next){
transition[prev][c]=duplicate;
prev=parent_link[prev];
}
parent_link[new_node]=parent_link[next]=duplicate;
}
}
if(id) insert_value(root[new_node],1,text_count,id);
return new_node;
}
void construct_parent_tree(){
for(int i=1;i<=total_nodes;i++)
children[parent_link[i]].push_back(i);
depth[0]=1;
dfs_traversal(0);
}
int locate_node(int u,int target_length){
u=position[u];
for(int i=20;i>=0;i--)
if(ancestor[u][i] && length[ancestor[u][i]]>=target_length)
u=ancestor[u][i];
return u;
}
void process_query()
{
int start,end,left,right;
start=input,end=input,left=input,right=input;
int target_root=root[locate_node(right,right-left+1)];
MaxInfo result=query_range(target_root,start,end,1,text_count);
if(!result.value) result.idx=start;
output(result.idx);putchar(' ');output(result.value);newline;
}
}automaton;
signed main()
{
automaton.parent_link[0]=-1;
scanf(" %s",base+1);
base_length=strlen(base+1);
text_count=input;
for(int i=1;i<=text_count;i++){
scanf(" %s",text+1);
current_pos=0;
for(int j=1;text[j];j++)
current_pos=automaton.add_character(text[j]-'a'+1,i);
}
current_pos=0;
for(int i=1;i<=base_length;i++)
position[i]=current_pos=automaton.add_character(base[i]-'a'+1,0);
automaton.construct_parent_tree();
int queries;queries=input;
while(queries--) automaton.process_query();
return 0;
}