AGC006 A Prefix and Suffix 解説
内容は問題文の通り。
・解説
s,tの文字列の長さは共にNで共通である。題意を満たすには、文字列sの後ろの部分文字列と、文字列tの前の部分文字列がどの程度被るかを調べればいい。
1つ目のテストケースで例えれば、
1回目
s: ○○c
t: c○○
2回目
s: ○bc
t: cd○
3回目
s: abc
t: cde
のような順で確認していく。この中で、一番文字列が被る長さが長いものを取得しておく(コードではlength)。ここでは1回目が同じ"c"で、それ以降は被らない。
最後に、N*2-[被る最大の文字列長]が答えになる。
コードでは、string::substr(開始点, 何文字抜き出すか) を使って文字列を抜き出して、比較している。例えば、s.substr(s.begin()+5, 6)なら、5文字目から6文字先まで抜き出してくれる。
int main(){ int n; string s,t; cin>>n>>s>>t; int length=0; rep(i,0,n+1){ //sは後ろから抜き出す、tは前から抜き出す //抜き出す長さをループで伸ばしていき、被る最大の文字列長をlengthに入れる if(s.substr(n-i,i)==t.substr(0,i)) length=i; } cout<<n*2-length<<endl; return 0; }