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

#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";
    }
}