52 lines
1.3 KiB
C++
52 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
//b是不是a的前缀
|
||
bool isPrefix(string a, string b) {
|
||
if (b.size() > a.size()) return false;
|
||
return a.substr(b.size()) == b;
|
||
}
|
||
|
||
//b是不是a的后缀
|
||
bool isSuffix(string a, string b) {
|
||
if (b.size() > a.size()) return false;
|
||
//substr(0,i) 从下标0开始，截取长度为i的子串
|
||
return a.substr(a.size() - b.size()) == b;
|
||
}
|
||
|
||
//合并两个字符串,最短相连
|
||
string merge(string a, string b) {
|
||
//遍历b字符串的所有前缀，看看a字符串是不是以这个前缀结尾
|
||
string pre;
|
||
for (int i = 1; i <= b.size(); i++) {
|
||
pre = b.substr(0, i);
|
||
if (isSuffix(a, pre))
|
||
break;//一旦找到就退出，这样，就保证是找到了最短的相连
|
||
}
|
||
if (pre == b) return "";
|
||
//拼接 substr(0,i) 从下标0开始，截取长度为i的子串
|
||
return a + b.substr(pre.size());
|
||
}
|
||
|
||
int main() {
|
||
string c = merge("beast", "astonish");
|
||
cout << c << endl;
|
||
|
||
c = merge("cheat", "tact");
|
||
cout << c << endl;
|
||
|
||
c = merge("cheat", "choose");
|
||
cout << c << endl;
|
||
|
||
c = merge("envelope", "envelope");
|
||
cout << c << endl;
|
||
|
||
c = merge("abababab", "abababc");
|
||
cout << c << endl;
|
||
|
||
c = merge("abababab", "abababab");
|
||
cout << c << endl;
|
||
|
||
return 0;
|
||
} |