問題はこちら
No.588 空白と回文 - yukicoder
まず線対称の軸となるべき場所を固定する。
（そのような場所は、文字の中心か、文字と文字の間となる）
中心から外側へ向かって、各文字が回文を構成するかどうかをチェックする。
中心に対して対称な位置にある文字が同じでない場合、それは空白にするしかなく、同じ場合は残すことで、最大の長さの文字列を得ることができる。
char s[1010]; l,r,m,k,M,n; main(){ n=strlen(gets(s)); for(m=0;m<2*n;m++){// m/2文字目を軸とする（例えば「1/2文字目」は0文字目と1文字目の間を表す） k=0; for(l=m/2,r=m-l;l>=0&&r<n;l--,r++)if(s[l]==s[r])k+=l==r?1:2; if(M<k)M=k; } printf("%d",M); }
この方針で縮めると次のようになる
char s[1010]; l,m,k,M,n; main(r){ for(n=strlen(gets(s));m<2*n;l=++m/2,M=fmax(M,2*k-m%2)) for(r=m-l,k=0;~l&&s[r];)k+=s[l--]==s[r++]; printf("%d",M); }
別の方針の方が短くなる。
まず軸を固定するところは同じだが、そのあとの探索を「元の文字列の各文字について」行っていく。
もとの文字列でi番目の文字は、対称の軸がm/2にあるとき、m-i文字目と対応するので、これが一致するかどうかを見る
char s[1010]; n,m,M,i,k; main(){ n=strlen(gets(s)); for(m=0;m<2*n;m++){//対称の軸 k=0; for(i=0;i<n;i++)if(m>=i&&m-i<n&&s[i]==s[m-i])k++; //i文字目のうつる先が元の文字列の中であり、文字が一致している時にのみ、回文を構成する if(M<k)M=k; } printf("%d",M); }
これをぎゅっとする
char s[1010]; m,M,i,k; main(n){ for(n=strlen(gets(s));m<2*n;M<c?M=c:0,c=i=0,m++) for(;i<n;i++)c+=m>=i&m-i<n&s[i]==s[m-i]; printf("%d",M); }
for文圧縮
for(n=strlen(gets(s));m<2*n;M<c?M=c:0,c=i=0,m++)for(;i<n;i++)c+=m>=i&m-i<n&s[i]==s[m-i]; for(n=strlen(gets(s));i<n?c+=m>=i&m-i<n&s[i]==s[m-i],++i:(M<c?M=c:0,c=i=0,++m<2*n);); for(n=strlen(gets(s));c+=m>=i&m-i<n&s[i]==s[m-i],++i<n?:(M<c?M=c:0,c=i=0,++m<2*n););
最後に配列サイズをごまかして完成
char s[9]; m,M,i,c; main(n){for(n=strlen(gets(s));c+=m>=i&m-i<n&s[i]==s[m-i],++i<n||(M<c?M=c:0,c=i=0,++m<2*n););printf("%d",M);}
126B
