最短串（思维 + 简单模拟）

清疚 2022-09-10 10:21 144阅读 0赞

链接：https://ac.nowcoder.com/acm/contest/20263/B  
来源：牛客网

题目描述 :  
给定22个由小写字母和问号组成的字符串a与b，问号代表你想要的任何字符。

请你找出最短的字符串s，要求s包含a和b两个字符串，你只需要输出s的长度即可。

队友和我说，一前一后直接拼接，把相同的部分直接减掉。

数组开小，wa了一发

// Problem: 最短串
    // Contest: NowCoder
    // URL: https://ac.nowcoder.com/acm/contest/20263/B
    // Memory Limit: 524288 MB
    // Time Limit: 2000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define ff first
    #define ss second
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b; i>=a; --i)
    typedef pair<int,int> PII;
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int inf=0x3f3f3f3f;
    const int N=5e3+100;
    int n;
    char a[N], b[N];
    
    void solve()
    { 
    	cin >> a >> b;
    	
    	int la = strlen(a), lb = strlen(b);
    	
    	int ans =  la+lb;
    	
    	for(int i=0; i<la; i++)
    	{ 
    		int l = i, r = 0;
    		while(l < la and r < lb and (a[l]==b[r] or a[l] == '?' or b[r] == '?'))
    		{ 
    			l++;
    			r++;
    		}
    		if(l==la) ans = min(ans, la+lb-(l-i));
    		if(r==lb) ans = min(ans, la);
    	}
    	for(int i=0; i<lb; i++)
    	{ 
    		int l = i, r = 0;
    		while(l < lb and r < la and (b[l]==a[r] or b[l] == '?' or a[r] == '?'))
    		{ 
    			l++;
    			r++;
    		}
    		if(l==la) ans = min(ans, la+lb-(l-i));
    		if(r==lb) ans = min(ans, la);
    	}
    	cout << ans << endl;
    }
    
    int main()
    { 
    	ios::sync_with_stdio(false);cin.tie(0);
    	solve();
    	return 0;
    }