PKU 1580 String Matching
http://poj.org/problem?id=1580
重なり具合を数える。
main(){ string a,b; while(cin>>a){ if(a=="-1")break; cin>>b; int p=SZ(a)+SZ(b),c=0; rep(i,SZ(a)){ int tc=0; rep(j,SZ(b)){ if(i+j<SZ(a) && a[i+j]==b[j])++tc; } c=max(tc*2,c); } rep(i,SZ(b)){ int tc=0; rep(j,SZ(a)) if(i+j<SZ(b) && b[i+j]==a[j])++tc; c=max(tc*2,c); } cout<<"appx("<<a<<','<<b<<") = "; if(c==0)cout<<0; else if(p==c)cout<<1; else cout<<c/__gcd(p,c)<<'/'<<p/__gcd(p,c); cout<<endl; } }