# 【題解】HDU 1867 A + B for you again

【題目敘述】https://vjudge.net/problem/HDU-1867
【解題想法】KMP (Knuth–Morris–Pratt algorithm)

#include <iostream>
#include <string>
using namespace std;

int f[100005], n, m, pos;
string s1, s2;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> s1 >> s2){
pos = -1;
f[0] = -1;
for (int i = 1; i < s2.length(); i++){
while (~pos && s2[i] != s2[pos+1]) pos = f[pos];
if (s2[i] == s2[pos+1]) pos++;
f[i] = pos;
}
pos = -1;
for (int i = 0; i < s1.length(); i++){
if (pos+1 == s2.length()) pos = f[pos];
while (~pos && s1[i] != s2[pos+1]) pos = f[pos];
if (s1[i] == s2[pos+1]) pos++;
}
n = pos+1;
pos = -1;
for (int i = 1; i < s1.length(); i++){
while (~pos && s1[i] != s1[pos+1]) pos = f[pos];
if (s1[i] == s1[pos+1]) pos++;
f[i] = pos;
}
pos = -1;
for (int i = 0; i < s2.length(); i++){
if (pos+1 == s1.length()) pos = f[pos];
while (~pos && s2[i] != s1[pos+1]) pos = f[pos];
if (s2[i] == s1[pos+1]) pos++;
}
m = pos+1;
if (n != m){
if (n > m) cout << s1 << s2.substr(n, s2.length()-n) << "\n";
else cout << s2 << s1.substr(m, s1.length()-m) << "\n";
}
else{
string s3 = s1+s2.substr(n, s2.length()-n), s4 = s2+s1.substr(m, s1.length()-m);
if (s3 > s4) cout << s4 << "\n";
else cout << s3 << "\n";
}
}
}
#include <iostream>
#include <vector>
using namespace std;

void build(string &t, vector<int> &F) {
F[0] = -1;
for (int i = 1, pos = -1 ; i < t.size() ; i++) {
while (~pos && t[i] != t[pos + 1])
pos = F[pos];

if (t[i] == t[pos + 1])
pos++;

F[i] = pos;
}
}

int match(string &s, string &t, vector<int> &F) {
int pos = -1;
for (int i = 0 ; i < s.size() ; i++) {
if (pos + 1 == (int)t.size()){
pos = F[pos];
}
while (~pos && s[i] != t[pos + 1])
pos = F[pos];

if (s[i] == t[pos + 1])
pos++;
}
return pos+1;
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s1, s2;
while (cin >> s1 >> s2){
vector<int> F2(s2.size());
build(s2, F2);
int l1 = match(s1, s2, F2);

vector<int> F1(s1.size());
build(s1, F1);
int l2 = match(s2, s1, F1);

string ans1 = s1 + s2.substr(l1, s2.size()-l1);
string ans2 = s2 + s1.substr(l2, s1.size()-l2);
if (ans1 < ans2) swap(ans1, ans2);

if (ans1.size() < ans2.size())
cout << ans1 << "\n";
else
cout << ans2 << "\n";
}
}