Problem: Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

5 3 2
aaaaa
aaa
aab


Output

1 6

Solution (in CPP):

Solution:
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int m;
int idx;
string s;

string expr();

int number(){
	int a=0;
	for(;s[idx]!='(';idx++){
		a=10*a+(s[idx]-'0');
		a=min(a,m);
	}
	return a;
}

string expr2(){
	if(isdigit(s[idx])){
		int num=number();
		idx++;
		string a=expr();
		idx++;

		string res;
		if(a.length()<m){
			rep(i,num){
				if(res.length()>=m) break;
				res+=a;
			}
		}
		else{
			res=a;
			num--;
			if(num>0){
				res+=a.substr(0,m);
				res+='@';
				res+=a.substr(a.length()-m,m);
			}
		}
		return res;
	}
	else return string(1,s[idx++]);
}

string expr(){
	string res;
	while(idx<s.length() && (isdigit(s[idx]) || islower(s[idx]))) res+=expr2();
	return res;
}

void regularize(string &s){
	::s=s;
	idx=0;
	s=expr();
}

class suffix_array{
	const static int N_MAX=200000;
	char s[N_MAX+1];
	int n,sa[N_MAX+1];

	int f[N_MAX+1];
	bool inc[N_MAX+1];

	struct cmp0{
		char *s;
		cmp0(char *s):s(s){}
		bool operator()(int i,int j){ return s[i]<s[j]; }
	};
	struct cmp1{
		int h,*f;
		cmp1(int h,int *f):h(h),f(f){}
		bool operator()(int i,int j){ return i==j||f[i]!=f[j]?f[i]<f[j]:f[i+h]<f[j+h]; }
	};

public:
	void build(const char *ss){
		n=strlen(ss);
		rep(i,n+1){
			s[i]=ss[i];
			sa[i]=i;
		}

		cmp0 c0(s);
		sort(sa,sa+n+1,c0);
		f[sa[0]]=0;
		rep(i,n) f[sa[i+1]]=f[sa[i]]+(c0(sa[i],sa[i+1])?1:0);

		for(int h=1;f[sa[n]]<n;h<<=1){
			cmp1 c1(h,f);
			sort(sa,sa+n+1,c1);
			rep(i,n) inc[i+1]=c1(sa[i],sa[i+1]);
			rep(i,n) f[sa[i+1]]=f[sa[i]]+(inc[i+1]?1:0);
		}
	}

	int calc_lcp(char *a,char *b){
		int i;
		for(i=0;a[i]&&b[i]&&a[i]==b[i];i++);
		return i;
	}

	int solve(char *t){
		int res=0,len;
		for(len=::m;len;len--,t++){
			int lo=0,hi=n;
			while(lo<hi){
				int mi=(lo+hi)/2;
				if(strcmp(t,s+sa[mi])<0) hi=mi; else lo=mi+1;
			}

			int tmp=calc_lcp(t,s+sa[lo]);
			if(lo>0) tmp=max(tmp,calc_lcp(t,s+sa[lo-1]));
			if(lo<n) tmp=max(tmp,calc_lcp(t,s+sa[lo+1]));
			res+=tmp;
		}
		return res;
	}
};

int main(){
	int n,k;
	string s; cin>>n>>m>>k>>s;

	regularize(s);

	static suffix_array SA;
	SA.build(s.c_str());

	int ans=-1,i_ans=-1;
	rep(i,k){
		char t[401]; cin>>t;
		int tmp=SA.solve(t);
		if(ans<tmp) ans=tmp, i_ans=i;
	}
	printf("%d %d\n",i_ans+1,ans);

	return 0;
}