立命館合宿2012 day3 問題F Icy Composer (AOJ 2367)

AOJ 構文解析 文字列

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2367）


2(3(b)4(ab)x)
のように圧縮された文字列sが与えられる。
tの空でない全ての連続する部分文字列のうち、展開後のsに含まれるものはいくつあるか
を求める問題。

制約条件

n≦250
m≦400
k≦5

方針

文字列を愚直に展開すると2(2(2(2(……))))などという場合に展開しきれなくなる。


mが400以下であることに注目し、
適当な部分だけを展開する。


An(B)Cのような文字列は
A + Bの先頭+ (区切り) + Bの末尾 + B + Bの先頭 + (区切り) + Bの末尾 + C
のように展開すればいい。
ここで、先頭、末尾は400文字までしか持たなくてよい。
そうすれば、一度のn()の展開で、最大で1600文字程度しか増えないので、
展開しきることができる。


区切りは文字列中に絶対に現れない文字を適当に選んで挿入する。
Bが短い場合、
An(B)CのAとCがつながる場合があるので、
上のように区切り文字を入れてしまうと、AとCがつながらなくなってしまう。
なので、n(B)が短い場合（400文字以上だったらつながらない）は、
直接展開するようにする。


文字列を展開しおえたら、
tの全ての部分文字列（400*400/2 = 8万個程度）について、
sに出現するかを調べる。
これはナイーブにやるとTLEなので、sのsuffix arrayを作って適当に高速に検索する。

ソースコード

// Larsson-Sadakane's Suffix array Construction: O(n (log n)^2)
struct SAComp {
  const int h, *g;
  SAComp(int h, int* g) : h(h), g(g) {}
  bool operator() (int a, int b) {
    return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
  }
};
int *buildSA(char* t, int n) {
  int g[n+1], b[n+1], *v = new int[n+1];
  rep(i,n+1) v[i] = i, g[i] = t[i];
  b[0] = 0; b[n] = 0;

  sort(v, v+n+1, SAComp(0, g));
  for(int h = 1; b[n] != n ; h *= 2) {
    SAComp comp(h, g);
    sort(v, v+n+1, comp);
    rep(i, n) b[i+1] = b[i] + comp(v[i], v[i+1]);
    rep(i, n+1) g[v[i]] = b[i];
  }
  return v;
}
// Naive matching O(m log n)
int find(char *t, int n, char *p, int m, int *sa) {
  int a = 0, b = n;
  while (a < b) {
    int c = (a + b) / 2;
    if (strncmp(t+sa[c], p, m) < 0) a = c+1; else b = c;
  }
  return strncmp(t+sa[a], p, m) == 0 ? sa[a] : -1;
}
int n,m,k;
string s;
char *sc,t[500];
int *sa,len;

ll ck(){
	ll res=0;
	for(int l=0,r=0;l<m;l++){
		while(r<l)r++;
		while(r<m){
			char tmp=t[r+1];
			t[r+1]=0;
			bool res=find(sc,len,t+l,r-l+1,sa)>=0;
			t[r+1]=tmp;
			if(!res)break;
			r++;
		}
		res+=r-l;
	}
	return res;
}

const string rec(int l,int r){
	if(l>=r)return "";
	
	if(isdigit(s[l])){
		int i,x=0,d=0;
		for(;l<r&&isdigit(s[l]);l++){
			x*=10; x+=s[l]-'0';
			x=min(x,400);
		}
		for(i=l;i<r;i++){
			if(s[i]=='(')d++;
			if(s[i]==')')d--;
			if(d==0)break;
		}
		string res="", tmp=rec(l+1,i);
		if(x==1)return tmp;
		
		rep(i,x-1){
			res+=tmp;
			if(res.size()>400)break;
		}
		const string str=res+tmp;
		if(str.size()<=800)return str+rec(i+1,r);
		const string head400=str.substr(0,min((int)str.size(),400));
		const string tail400=str.substr(max(0,(int)str.size()-400));
		
		const string tail=tmp.substr(max(0,(int)tmp.size()-400));
		const string head=tmp.substr(0,min(400,(int)tmp.size()));
		
		return head400+"@"+tail+res+head+"@"+tail400+rec(i+1,r);
	}
	return s[l]+rec(l+1,r);
}
int main(){
	cin>>n>>m>>k;
	cin>>s;
	s=rec(0,n);
	len=s.size();
	sc=(char*)malloc(len+1);
	sprintf(sc,"%s",s.c_str());
	sa=buildSA(sc,len);
	
	int ansi=0; ll ans=0;
	rep(i,k){
		cin>>t;
		ll tmp=ck();
		if(tmp>ans)ans=tmp, ansi=i;
	}
	cout<<ansi+1<<" "<<ans<<endl;
	
	return 0;
	
}