PKU 3192 DNA Assembly
http://poj.org/problem?id=3192
n個の文字列全てを連続する部分文字列として含むような文字列の最小の長さを求めるというような問題。
cinやstringに頼ってやったら、TLEだったので、頑張ってCっぽく書いてみました。
str***系の関数はやっぱりかなり早いみたいですね。
char in[7][10]; int szin[7]; int per[7]; char tstr[100]; main(){ int n; int ans=0; scanf("%d",&n); rep(i,n){ scanf("%s",in[i]); szin[i]=strlen(in[i]); ans+=szin[i]; per[i]=i; } do{ tstr[0]=0; strcat(tstr,in[per[0]]); int szt=szin[per[0]]; for(int i=1;i<n;++i){ int ol=0; for(int j=min(szt,szin[per[i]]);j;--j){ if(strncmp(tstr+szt-j,in[per[i]],j)==0){ ol=j; break; } } strcat(tstr+szt,in[per[i]]+ol); szt+=szin[per[i]]-ol; } ans=min(ans,szt); }while(next_permutation(per,per+n)); printf("%d\n",ans); }