2014
03-07

# Compressed String

Dealing with super long character strings is Chris’s daily work. Unfortunately, the strings are so long that even the fastest computer in the world cannot work with them.Chris does her work in a smart way by compressing the strings into shorter expressions. She does her compression for each string in the following way:

a) Find a consecutive repeated substring of the original string, e.g. “ab” in “cabababd”.

b) Replace the repeating part with the bracketed repetend, followed by the times the repetend appears in the original string. e.g. Write “cabababd” as “c[ab]3d”. Note she can also write it as “c[ab]1ababd” or “ca[ba]2bd” and so on, although these string are not compressed as well as the first one is.

c) Repeat a) and b) several times until the string is short enough.

Chris does her compression quite well. But as you know, the work is boring and a waste of time. Chris has written a computer program to help her do the boring work. Unfortunately, there is something wrong with the program; it often outputs an incorrect result. To help her debug the program, you are ordered to write a debugger which can compare Chris’s standard compressed string against the string compressed by the program.

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.For each test case, there are two lines of character strings which the first one is Chris’s standard compressed string and the second one is the program’s compressed string. Both string contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9). The brackets must be followed with an integer indicating the times the string in the brackets repeat, note that the repeat time can be zero. The brackets can be nested.
You can assume all the compressed strings in the input are no longer than 20.
See further details in the input sample.

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.For each test case, there are two lines of character strings which the first one is Chris’s standard compressed string and the second one is the program’s compressed string. Both string contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9). The brackets must be followed with an integer indicating the times the string in the brackets repeat, note that the repeat time can be zero. The brackets can be nested.
You can assume all the compressed strings in the input are no longer than 20.
See further details in the input sample.

5
a[a]12
[[a]3]4a
[z]12
zzzzzzzzz
[a[ba]2b]12
[ab]36
[a]123123123[icpc]2
[[a]123]1001001inter
aismoreeasierthanc
gismuchharderthanj

Case #1: YES
Case #2: NO 10
Case #3: YES
Case #4: NO 123123125
Case #5: NO 1
Hint

For sample test case 3, the first string “[a[ba]2b]12” can be written as “[ababab]12”, then “[[ab]3]12”, finally we get “[ab]36”. The numbers in this task may be very large and cannot be stored in a 32 bit integer.

pascal的过了SPOJ和acmicpc，HDU死活不过
cpp过了SPOJ和hdu，acmicpc死活过不了

SPOJ比较正常，HDU专门卡PAS的字符串读入，我擦，acmicpc大概比较奇葩，我pascal秒过而且rank1

BKDR是什么？乃们自己看吧，大概就是两个质数乘法，乘方再取模 http://www.byvoid.com/blog/hash-compare/

/*
Author : zxybazh
Date   : 2012/10/31
Soure  : Compressed String hdu_3222
*/

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define LL long long

using namespace std;

char s[10][1001];
LL kk,tmp,n,m;
LL k,t,ans;
LL mo[10],p[10];
LL num[10][101],sum[10][101],cp[10][101];
LL en[10][101];

LL work(LL p,LL x){
LL tmp=1;
LL d=0;
for (;x!=0; x >>= 1){
if (x & 1) tmp=tmp * cp[p][d]% mo[p];
d++;
}
return tmp;
}

void extended_gcd(LL a, LL b,LL &x,LL &y){
LL tmp;
if (b==0) {
x=1;y=0;
}
else{
extended_gcd(b,a % b,x,y);
tmp=y;y=x-a / b*y;x=tmp;
}
}

LL ny(LL d,LL b){
LL tmp,tt;
extended_gcd(b,mo[d],tt,tmp);
return tt;
cout << tt <<endl;
}

LL get(LL sx,LL num, LL d,LL gb){
return(sx * (( work (d , gb * num) + mo[d] -1) % mo[d]) % mo[d]
* ((ny(d,work(d,gb) + mo[d] - 1)) % mo[d] + mo[d]) % mo[d]);
}

void solve(LL d,LL l,LL r,LL le,LL &t1,LL &t2){
LL i,k1,k2,t;
t1=0;t2=0;t=0;i=l;
while ( le > t && i <= r) {
if (s[d][i]!='['){
t++;
t1=(t1 * p[1] + s[d][i])% mo[1];
t2=(t2 * p[2] + s[d][i])% mo[2];
i++;
continue;
};
if (t+sum[d][i]*num[d][i]<=le) {
solve(d,i+1,en[d][i]-1,le,k1,k2);
k1=get(k1,num[d][i],1,sum[d][i]);
k2=get(k2,num[d][i],2,sum[d][i]);//first num which p gongbi
t1=(t1*work(1,num[d][i]*sum[d][i])+k1 % mo[1]) % mo[1];
t2=(t2*work(2,num[d][i]*sum[d][i])+k2 % mo[2]) % mo[2];
t+=sum[d][i]*num[d][i];
i=en[d][i]+1;
while (i<=r && s[d][i]>='0' && s[d][i]<='9') i++;
} else
if (t+sum[d][i]>=le) {
solve(d,i+1,en[d][i]-1,le-t,k1,k2);
t1=(t1*work(1,le-t)+k1 % mo[1]) % mo[1];
t2=(t2*work(2,le-t)+k2 % mo[2]) % mo[2];
t=le;
}
else{
solve(d,i+1,en[d][i]-1,le-t,k1,k2);
k1=get(k1,(le-t) / sum[d][i],1,sum[d][i]);
k2=get(k2,(le-t) / sum[d][i],2,sum[d][i]);
t1=(t1*work(1,(le-t) / sum[d][i]*sum[d][i])+k1 % mo[1]) % mo[1];
t2=(t2*work(2,(le-t) / sum[d][i]*sum[d][i])+k2 % mo[2]) % mo[2];
t+=((le-t) / sum[d][i] * sum[d][i]);
solve(d,i+1,en[d][i]-1,le-t,k1,k2);
t1=(t1*work(1,le-t)+k1 % mo[1]) % mo[1];
t2=(t2*work(2,le-t)+k2 % mo[2]) % mo[2];
t=le;
};
}
//cout<< d<<' '<<l<<' '<<r<<' '<<le<<' '<<t1<<' '<<t2<<endl;
}

bool check(LL x){
LL t1,t2,k1,k2;
solve(1,0,strlen(s[1])-1,x,t1,t2);
solve(2,0,strlen(s[2])-1,x,k1,k2);
if (t1==k1 && t2==k2) return true; else return false;
}

void tc(LL l,LL r){
LL mid;
while (l<=r) {
mid=(l+r)/2;
if (not check(mid)){
if (mid<ans) ans=mid;
r=mid-1;
}
else l=mid+1;
}
}

LL calc(LL d,LL l,LL r){
LL k,i,tmp;
LL kk,t;
t=0;i=l;
while (i<=r) {
if (s[d][i]!='[') {
t++;i++;continue;
}
tmp=0;
for (k=i+1;k<=r;k++){
if (s[d][k]==']' && tmp==0) break;
if (s[d][k]=='[')  tmp++;
if (s[d][k]==']')  tmp--;
}
kk=0;
tmp=k+1;
while (tmp<=r && s[d][tmp]>='0' && s[d][tmp]<='9') {
kk=kk * 10 + s[d][tmp]-'0';
tmp++;
}
en[d][i]=k;
sum[d][i]=calc(d,i+1,k-1);
num[d][i]=kk;
t+=sum[d][i]*num[d][i];
i=tmp;
}
return t;
}
int main(){
//freopen("compress.in", "r", stdin);
//freopen("compress.out", "w", stdout);

LL testcase;
scanf("%I64d\n",&testcase);

p[1]=131;
p[2]=1313;
mo[1]=23456789;
mo[2]=19891229;
for (LL i=1;i<3;i++){
cp[i][0]=p[i];
for (LL j=1;j<101;j++) cp[i][j]=(cp[i][j-1]*cp[i][j-1]) % mo[i];
}
//cout<<"yooooooooooo"<<endl;
for (LL kk=1;kk<=testcase;kk++){
cout<<"Case #"<<kk<<": ";
gets(s[1]);gets(s[2]);
k=calc(1,0,strlen(s[1])-1);
t=calc(2,0,strlen(s[2])-1);
if (k!=t){
if (t<k)k=t;
ans=k+1;
tc(1,k);
cout<<"NO ";
cout<<ans<<endl;
}
else{
ans=k+1;
tc(1,k);
if (ans==k+1) cout<<"YES"<<endl;
else cout<<"NO "<<ans<<endl;
}
}
}

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3