AT2162

Lithium_Chestnut · 2021-08-13 08:12:54 · 题解

首先简化一下这题的题意，很显然就是给你两个长度为 n 的字符串 a,b，要求你去掉重合部分后求新串长度：

如上图，圈内的代表重合部分，显然新串的长度就是 a 串长度 +\ b 串长度 - 重合部分（一份）。我们把重合部分的长度设为 \text{same}，那么我们要求的答案就是 n \times 2\ -\ \text{same}。

求 \text{same} 的过程，我们直接使用一层循环模拟，暴力寻找 a 的每一位，由于重合部分一定在 a 的末尾，b 的开头，所以我们要判定 \text{same} 的条件为 a_i=b_\text{same}。

那么至此，就大功告成了，时间复杂度 \text{O(n)}。

代码：

#include<bits/stdc++.h>
using namespace std;
string a,b;
int n,same;
int read()
{
    int x=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return w?-x:x;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
int main()
{
    n=read();
    cin>>a>>b;
    for(int i=0;i<n;i++)
    {
        if(a[i]==b[same]) same++;
    }   
    write(n*2-same);
    return 0;
}