「题解」AC自动机（简单版）

虽然说这题是AC自动机吧…但是后缀数组也能解。
在这里提供一个清新的后缀数组解法。

后缀数组

后缀数组是个好东西啊，通过这个工具可以解决许多类型的字符串问题，这里简单介绍一下：

形式化地，对于一个长度为 $n$ 的字符串 $s$，它的形如 $s[i:n]$ 的子串被称作 $s$ 的后缀。

容易发现 $s$ 一共有 $n$ 个后缀，不妨记 $s[i:n]$ 为后缀 $i$，将所有的后缀排序后，顺序写下后缀的编号，就得到了后缀数组 (Suffix Array)。

举个例子，对 $s=ababa$，其后缀有 $a,ba,aba,baba,ababa$，排序后得到 $a,aba,ababa,ba,baba$，依次写下其编号，得到后缀数组为 $5,3,1,2,4$。

朴素求后缀数组是 $O(n^2 \log n)$ 的，这显然是不太好的。通过倍增法去求，容易发现倍增的过程是某种双关键字排序，那么对其进行基数排序，可做到 $O(n \log n)$。具体的实现超出了本篇题解的范畴，请移步 后缀排序。

回到本题

容易发现，一个串 $s$ 若能与 $t$ 匹配，那么它必然是 $t$ 的 某个后缀的前缀。
我们可以快速把所有后缀都排序，这样后缀就是有序的了，可以通过二分来找 $s$ 是否与 $t$ 匹配。

具体实现上，因为后缀的长度和是 $O(n^2)$ 级别的，所以不能把他们全部搞出来（会MLE）。实际上只需要写一个 cmp() 函数来比较字符串大小就好了，实现起来比较清新易懂。

复杂度因为每次要二分，所以整体多了一个 $\log$，不过均摊下来跑的非常快，常数比AC自动机大了不到一半。

代码：

/* fake-acam.cpp */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 1e6 + 6;

char t[CN], s[CN];
string mem[CN];

int sa[CN], rk[CN << 1], prk[CN << 1], id[CN], px[CN], cnt[CN];
void SA(int n){
    int m = max(n, 300);
    for(int i = 1;i <= n;i++) rk[i] = t[i - 1];
    for(int i = 1;i <= n;i++) cnt[ rk[i] ] ++;
    for(int i = 1;i <= m;i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[ cnt[ rk[i] ]-- ] = i;
    for(int w = 1; w < n; w <<= 1){
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1;i <= n;i++) id[i] = sa[i];
        for(int i = 1;i <= n;i++) cnt[ px[i] = rk[ id[i] + w ] ]++;
        for(int i = 1;i <= m;i++) cnt[i] += cnt[i - 1];
        for(int i = n; i; i--) sa[ cnt[ px[i] ]-- ] = id[i];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1;i <= n;i++) id[i] = sa[i];
        for(int i = 1;i <= n;i++) cnt[ px[i] = rk[ id[i] ] ]++;
        for(int i = 1;i <= m;i++) cnt[i] += cnt[i - 1];
        for(int i = n; i; i--) sa[ cnt[ px[i] ]-- ] = id[i];
        memcpy(prk, rk, sizeof(rk)); m = 0;
        for(int i = 1;i <= n;i++)
            if(prk[ sa[i] ] == prk[ sa[i - 1] ] && prk[ sa[i] + w ] == prk[ sa[i - 1] + w ])
                rk[ sa[i] ] = m;
            else rk[ sa[i] ] = ++m;
        if(m == n) break;
    }
}

int n, lt;

// 判断 a[] < b[]
inline int le(char *a, char *b, int la,int lb){
    int p = 0;
    while(a[p] == b[p] && p < min(la, lb)) p++;
    if(p == lb) return -1;
    if(p == la) return true;
    return a[p] < b[p];
}

int main()
{
    // freopen("_in.in", "r", stdin);
    // freopen("out.txt", "w", stdout);
    
    scanf("%d", &n);
    for(int i = 1;i <= n;i++) cin >> mem[i];
    cin >> t; lt = strlen(t);

    SA(lt);
    
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        int ls = mem[i].size();
        s[ls] = '\0';
        for(int j = 0;j < ls;j++) s[j] = mem[i][j];

        int l = 1, r = lt, m; bool found = false;
        while(l < r){
            m = (l + r) >> 1;
            int leq = le(t + sa[m] - 1, s, lt - sa[m] + 1,ls);
            if(leq == -1) {found = true; break;}
            else if(leq) l = m + 1;
            else r = m;
        }

        cnt += found ? 1 : 0;
    }

    printf("%d", cnt);
}