Description
给定一个基础串 \(s\) 和若干个询问串 \(t\)。对于每一段文字 \(t\)，求出其最长的前缀 \(p\)，满足 \(p\) 是 \(s\) 的子串。
Solution
对 \(s\) 建立 SAM，把每个 \(t\) 扔到上面跑，跑不动了的时候，立即停止而不走 link，所积累的 \(len\) 就是答案
注意内存开满了会 MLE，适当开小一点
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 12000005;
int rep(char t) {
if(t==‘N‘) return 0;
if(t==‘S‘) return 1;
if(t==‘W‘) return 2;
if(t==‘E‘) return 3;
return 0;
}
struct Suffix_Automata {
int Size, Last;
int maxlen[Maxn], link[Maxn], trans[Maxn][4];
Suffix_Automata() {
Size = Last = 1;
}
inline void Extend(int id) {
int cur = (++ Size), p;
maxlen[cur] = maxlen[Last] + 1;
for (p = Last; p && !trans[p][id]; p = link[p]) trans[p][id] = cur;
if (!p) link[cur] = 1;
else {
int q = trans[p][id];
if (maxlen[q] == maxlen[p] + 1) link[cur] = q;
else {
int clone = (++ Size);
maxlen[clone] = maxlen[p] + 1;
for(int i=0;i<4;i++) trans[clone][i] = trans[q][i];
link[clone] = link[q];
for (; p && trans[p][id] == q; p = link[p]) trans[p][id] = clone;
link[cur] = link[q] = clone;
}
}
Last = cur;
}
int solve(string str) {
int p=1, tmp=0;
for(int i=0;i<str.length();i++) {
if(trans[p][rep(str[i])]==0) return i;
if(trans[p][rep(str[i])]) ++tmp, p=trans[p][rep(str[i])];
}
return str.length();
}
} sam;
int main() {
ios::sync_with_stdio(false);
int n;
string s;
int m;
string t;
cin>>n>>m>>s;
for(int i=0;i<n;i++) {
sam.Extend(rep(s[i]));
}
for(int i=1;i<=m;i++) {
cin>>t;
cout<<sam.solve(t)<<endl;
}
}