41 lines
1.0 KiB
C++
41 lines
1.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
//两个字符串，最小重叠部分的长度
|
||
string merge(string a, string b) {
|
||
int n = INF;
|
||
//相连接 两层循环找出a的所有可能子串，然后与b串的前缀进行对比，找到最长的
|
||
for (int i = a.size() - 1; i > 0; i--) {
|
||
string t = a.substr(i);
|
||
if (b.compare(0, t.size(), t) == 0) { //如果相等则输出为0，不等则输出为-1。
|
||
n = a.size() - i;//长度
|
||
break;
|
||
}
|
||
}
|
||
if (n < INF) return a + b.substr(n);
|
||
else return "";
|
||
}
|
||
|
||
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;
|
||
} |