字符串哈希, 从大到小枚举长度
#include <bits/stdc++.h>
using namespace std;
class HashString {
private:
typedef unsigned long long ull;
const int P = 131;
vector<ull> p;
vector<ull> prefix;
int n;
public:
HashString(string s) {
n = s.size();
s.insert(0, "0");
p.resize(n + 1), p[0] = 1;
prefix.resize(n + 1, 0);
for(int i=1; i<=n; i++) {
p[i] = p[i-1] * P;
prefix[i] = prefix[i - 1] * P + s[i];
}
}
ull get(int l, int r) {
return prefix[r] - prefix[l - 1] * p[r - l + 1];
}
};
int main () {
string s1, s2;
while (cin >> s1 >> s2) {
int len = min(s1.size(), s2.size());
int r = s2.size();
auto hs1 = HashString(s1), hs2 = HashString(s2);
while (len > 0) {
if (hs1.get(1, len) == hs2.get(r - len + 1, r)) {
break;
}
len --;
}
if (len) {
cout << s1.substr(0, len) << " ";
}
cout << len << endl;
}
return 0;
}