AGC006 A Prefix and Suffix 解説

・問題
A - Prefix and Suffix

内容は問題文の通り。

・解説
s,tの文字列の長さは共にNで共通である。題意を満たすには、文字列sの後ろの部分文字列と、文字列tの前の部分文字列がどの程度被るかを調べればいい。

１つ目のテストケースで例えれば、

１回目
s: ○○c
t: c○○

２回目
s: ○bc
t: cd○

３回目
s: abc
t: cde

のような順で確認していく。この中で、一番文字列が被る長さが長いものを取得しておく(コードではlength)。ここでは１回目が同じ"c"で、それ以降は被らない。

最後に、N*2-[被る最大の文字列長]が答えになる。

コードでは、string::substr(開始点, 何文字抜き出すか) を使って文字列を抜き出して、比較している。例えば、s.substr(s.begin()+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;
}