CVBB ACM Team

l1=strlen(a+1),l2=strlen(b+1);
nxt[1]=l2;
i=1;
while(b[i]==b[i+1]&&i+1<=l2) i++;
nxt[2]=i-1;
pos=2;
for(i=3;i<=l2;i++){
	if(pos+nxt[pos]>=i) nxt[i]=min(nxt[i-pos+1],pos+nxt[pos]-i);
	while(b[nxt[i]+1]==b[nxt[i]+i]) nxt[i]++;
	if(nxt[i]+i>pos+nxt[pos]) pos=i; 
}
pos=1;
int l=min(l1,l2);
for(i=1;i<=l;i++) {
	if(a[i]!=b[i]) break;
	extend[1]=i;
}
for(i=2;i<=l1;i++){
	if(pos+extend[pos]>=i) extend[i]=min(nxt[i-pos+1],pos+extend[pos]-i);
	while(extend[i]+1<=l2&&extend[i]+i<=l1&&b[extend[i]+1]==a[extend[i]+i]) extend[i]++;
	if(extend[i]+i>pos+extend[pos]) pos=i; 
}