思路与算法

把所有文字的前缀建Trie，并建立AC后缀失败链接。扫描母串时标记到达状态，按BFS编号逆序把标记传播到fail祖先，最后沿每个文字路径找最深被标记前缀。为满足完整范围64 MB限制，母串与文字字符均用2位打包、Trie按层生成BFS连续编号；每结点只存4位孩子掩码，用每16结点的rank检查点与popcount计算孩子编号，fail压成24位，标记压成位。临时分组表在建立fail前释放。

正确性说明

Trie结点表示某个文字前缀，fail链依次表示其最长真后缀前缀。扫描母串到达的最长匹配状态及全部fail祖先，恰是以当前位置结尾的所有文字前缀；逆BFS传播覆盖这些祖先且不引入未出现字符串。每个文字找最深标记即最长出现在母串内的前缀。压缩结构不改自动机：BFS层按父结点顺序排列孩子，孩子编号=1+此前所有父结点孩子数+本父亲较小字符的孩子数，rank和掩码精确算出此值。总结点≤1+总文字长≤10000001，小于2^24，故24位fail无截断。

复杂度

令L为文字总长、h≤100为最大文字长、W为实际Trie结点数。排序比较O(h M log M)，分层建树O(L)，保守失败链接/匹配上界O((W+N)h)，查询O(L)。空间O(N+M+L)：压缩母串约N/4字节（读入临时字符串随后释放），文字约40M字节，结点掩码/rank/fail/标记合计约3.875W字节；含预留数组和分层临时表初始化，临时表在fail阶段前释放。完整10^7母串、10^5条100长文字已按原64 MB预检。

易错点

不能暗加总文字长≤10^6限制。大小写固定ESWN，字符编码需前后一致；移位量始终小于64，24位编号按无符号字节组装。标记还要传播fail，单标到达状态会漏短前缀。 首次原生大点为MLE，已保留失败记录；本版进一步将母串压为2位字符，不减少数据、不提高64 MB限制，修复后必须重新核验原生结果。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

struct Pat {
    array<unsigned long long, 4> w;
    int len, id;
};
int letter(char c) {
    return c == 'E' ? 0 : c == 'N' ? 1 : c == 'S' ? 2 : 3;
}
int digit(const Pat &p, int i) {
    return (p.w[i / 32] >> (2 * (i % 32))) & 3;
}
int main() {
    int N, M;
    cin >> N >> M;
    string text;
    text.reserve(N);
    cin >> text;
    vector<unsigned long long> textbits((N + 31) / 32);
    for (int i = 0; i < N; i++)
        textbits[i / 32] |= (unsigned long long)letter(text[i]) << (2 * (i % 32));
    string().swap(text);
    vector<Pat> p(M);
    size_t total = 0;
    for (int i = 0; i < M; i++) {
        string s;
        cin >> s;
        p[i].w.fill(0);
        p[i].len = s.size();
        p[i].id = i;
        total += s.size();
        for (int j = 0; j < (int)s.size(); j++)
            p[i].w[j / 32] |= (unsigned long long)letter(s[j]) << (2 * (j % 32));
    }
    sort(p.begin(), p.end(), [](const Pat &a, const Pat &b) {
        int k = min(a.len, b.len);
        for (int i = 0; i < k; i++) {
            int x = digit(a, i), y = digit(b, i);
            if (x != y)
                return x < y;
        }
        return a.len < b.len;
    });
    vector<unsigned long long> masks;
    masks.reserve((total + 16) / 16);
    int nodes = 0;
    vector<pair<int, int>> cur, next;
    cur.reserve(M);
    next.reserve(M);
    cur.push_back({0, M});
    for (int depth = 0; !cur.empty(); depth++) {
        next.clear();
        for (auto range : cur) {
            int mask = 0, j = range.first;
            while (j < range.second && p[j].len == depth)
                j++;
            while (j < range.second) {
                int k = j + 1, c = digit(p[j], depth);
                while (k < range.second && digit(p[k], depth) == c)
                    k++;
                mask |= 1 << c;
                next.push_back({j, k});
                j = k;
            }
            if (nodes % 16 == 0)
                masks.push_back(0);
            masks.back() |= (unsigned long long)mask << (4 * (nodes % 16));
            nodes++;
        }
        cur.swap(next);
    }
    vector<pair<int, int>>().swap(cur);
    vector<pair<int, int>>().swap(next);
    vector<unsigned> rank(masks.size() + 1);
    for (int i = 0; i < (int)masks.size(); i++)
        rank[i + 1] = rank[i] + __builtin_popcountll(masks[i]);
    auto mask = [&](int u) {
        return int(masks[u / 16] >> (4 * (u % 16))) & 15;
    };
    auto child = [&](int u, int c) {
        int bits = mask(u);
        if (!(bits >> c & 1))
            return 0;
        int shift = 4 * (u % 16);
        unsigned long long lower = shift ? (masks[u / 16] & ((1ULL << shift) - 1)) : 0;
        return int(1 + rank[u / 16] + __builtin_popcountll(lower) +
                   __builtin_popcount((unsigned)(bits & ((1 << c) - 1))));
    };
    vector<unsigned char> fail((size_t)nodes * 3);
    auto getfail = [&](int u) {
        return int(fail[3 * u]) + (int(fail[3 * u + 1]) << 8) + (int(fail[3 * u + 2]) << 16);
    };
    auto setfail = [&](int u, int v) {
        for (int j = 0; j < 3; j++)
            fail[3 * u + j] = (v >> (8 * j)) & 255;
    };
    for (int u = 0; u < nodes; u++)
        for (int c = 0; c < 4; c++) {
            int v = child(u, c);
            if (!v)
                continue;
            if (!u) {
                setfail(v, 0);
                continue;
            }
            int f = getfail(u);
            while (f && !child(f, c))
                f = getfail(f);
            setfail(v, child(f, c));
        }
    vector<unsigned long long> seen((nodes + 63) / 64);
    auto mark = [&](int u) {
        seen[u / 64] |= 1ULL << (u % 64);
    };
    auto was = [&](int u) {
        return (seen[u / 64] >> (u % 64)) & 1ULL;
    };
    int state = 0;
    for (int i = 0; i < N; i++) {
        int c = (textbits[i / 32] >> (2 * (i % 32))) & 3, v = child(state, c);
        while (state && !v) {
            state = getfail(state);
            v = child(state, c);
        }
        state = v;
        mark(state);
    }
    for (int u = nodes - 1; u > 0; u--)
        if (was(u))
            mark(getfail(u));
    vector<int> ans(M);
    for (auto pat : p) {
        int state = 0, best = 0;
        for (int j = 0; j < pat.len; j++) {
            state = child(state, digit(pat, j));
            if (was(state))
                best = j + 1;
            else
                break;
        }
        ans[pat.id] = best;
    }
    for (int v : ans)
        cout << v << "\n";
}