洛谷。
题目传送门。
放一个好像没人写的哈希做法。复杂度比较劣，但个人认为很简单。为什么不写 SA？因为我不会。
设两个串为 \(s_1,s_2\)，其中 \(s_2\) 为较长的一个。
发现答案必然介于 \(0\) 和 \(|s_1|\) 之间。于是我们用二分的方式枚举答案，这一步是 \(O(\log n)\) 的。
考虑对于枚举到的每个答案 \(k\)，应该如何判断是否存在长度为 \(k\) 的公共子串。下面所说“某串的子串”均默认这一子串的长度为 \(k\)。
我们发现，在任何一个串里，长度为 \(k\) 的子串至多有 \(O(n)\) 种，所以我们可以先把两个串的所有长度为 \(k\) 的子串找出来，再判断是否有一个 \(s_1\) 的子串和一个 \(s_2\) 的子串相等。要找出所有长为 \(k\) 的子串，这一步是 \(O(n)\) 的。
这里就涉及到了字符串间的比较。因此我们预处理出两个串的每个前缀的哈希值，这一步是 \(O(n)\) 的；后面每一次比较都把预处理的哈希值拿出来用即可，这一步是 \(O(1)\) 的。
这时我们发现，两两枚举两边的子串会产生 \(O(n^2)\) 次比较，总复杂度退化到 \(O(n^2 \log n)\)。这是我们不希望看到的，考虑如何降低复杂度。
容易想到开一个 unordered_map 来标记在所有 \(s_1\) 的子串中出现过的哈希值，然后将所有 \(s_2\) 的子串的哈希值遍历一遍；若某一 \(s_2\) 的子串哈希值已经出现过，那这个 \(k\) 是合法的。um 的期望复杂度是 \(O(1)\)，因此这一步是 \(O(n)\) 的，总复杂度 \(O(n \log n)\)。
然而由于 um 的神秘最坏复杂度，上面这个做法会 TLE。换成复杂度稳定在 \(O(\log n)\) 的 map 也没有用，因为总复杂度退化到了 \(O(n\log^2 n)\)，且常数太大。
我们忽视 gp_hash_table 这一类我不会写的东西，考虑别的做法。
我们发现双指针比较擅长将这种 \(O(n^2)\) 次的比较降到 \(O(n)\) 次。于是我们用两个 vector 存下两个串的子串的哈希值，分别排序，然后做一遍双指针即可。排序的复杂度是 \(O(n\log n)\)，双指针求解的复杂度是 \(O(n)\)，因此总复杂度是 \(O(n\log^2 n)\)，略低于 \(10^8\)。
由于没有用什么常数特别大的 STL，简单卡一下常（像这样），就可以过了。
上面的文字内容应该很好懂，所以代码就不加注释了。
#pragma GCC optimize("3,Ofast,unroll-loops")
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define ull unsigned long long
using namespace std;const int N=2.5e5+5;int n1,n2;
char s1[N],s2[N];namespace sto_HASHGOD_orz{const ull b=1013;ull pw[N];ull val1[N],val2[N];inline ull mul(ull a,ull b){return a*b;}inline void init(){if(strlen(s1+1)>strlen(s2+1))swap(s1,s2);n1=strlen(s1+1),n2=strlen(s2+1);pw[0]=1;for(int i=1;i<=n2;++i)pw[i]=mul(pw[i-1],b);for(int i=1;i<=n1;++i)val1[i]=(mul(val1[i-1],b)+s1[i]);for(int i=1;i<=n2;++i)val2[i]=(mul(val2[i-1],b)+s2[i]);return ;}inline ull qry1(int l,int r){return val1[r]-mul(val1[l-1],pw[r-l+1]);}inline ull qry2(int l,int r){return val2[r]-mul(val2[l-1],pw[r-l+1]);}}using namespace sto_HASHGOD_orz;inline bool chk(int mid){vector<ull>v1,v2;for(int i=1;i+mid-1<=n1;++i)v1.push_back(qry1(i,i+mid-1));for(int i=1;i+mid-1<=n2;++i)v2.push_back(qry2(i,i+mid-1));int i=0,j=0;while(i<v1.size()&&j<v2.size()){while(v1[i]<v2[j]&&i<v1.size())++i;while(v1[i]>v2[j]&&j<v2.size())++j;if(v1[i]==v2[j])return 1;}return 0;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>(s1+1);cin>>(s2+1);init();int l=0,r=n1;while(l<r){int mid=(l+r+1)>>1;if(chk(mid))l=mid;else r=mid-1;}return cout<<r<<"\n",0;
}/*%%%sto jiangly orz%%%
%%%sto tourist orz%%%
%%%sto nzhtl144777 orz%%%
%%%sto MoTao orz%%%
%%%sto zhoukangyang orz%%%
%%%sto FanHaoqiang orz%%%
%%%sto ChenDanqi orz%%%
%%%sto hdyzyx orz%%%
%%%sto s_o_t_b orz%%%
%%%sto dottle orz%%%
%%%sto Social_Zhao orz%%%
%%%sto final_trump orz%%%
%%%sto stntn orz%%%
%%%sto zyn0309 orz%%%
%%%sto xzy_sf orz%%%
%%%sto jerry1717 orz%%%
%%%sto Statax orz%%%
%%%sto fengzhaoyu orz%%%
%%%sto XXh0919 orz%%%
%%%sto shiziyu111 orz%%%
%%%sto xiangxiyu orz%%%
%%%sto xzf110618 orz%%%
%%%sto Lywh_ddAC orz%%%
%%%sto yiming1123 orz%%%
%%%sto zhouwenbo1234 orz%%%*/
不知道 SPOJ 怎么挂提交记录的链接，所以我就放了个图。
