牛客周赛 Round 103F

已经看到出题人的trie+二分哈希做法，以及前排大佬根号分治，长串Z函数，短串暴力trie。

给出一种AC自动机做法：

• 对于一个的后缀 ， 答案为 ，其中 代表 是多少个 的前缀。因为题目要求的是 "每个字符串的最长公共前缀的长度之和。" 那么的每个长度的前缀 若能匹配上 个 ，那么对于长度之和的贡献就是 。

• 于是对 集合建出AC自动机，那么自动机（本质上是Trie树）上根到每个结点这条链，代表了一个 集合中的前缀。对于这些前缀，我们只需考量它是否在 中出现，那么答案就可以取到这条链中的所有前缀，也就是上面的 的前缀和。

using namespace std;
#define vii vector<int>

const int maxn = 1e6 + 5;
constexpr int N = 1e6 + 6;
constexpr int LEN = 1e6 + 6;
constexpr int SIZE = 1e6 + 6;

string s,t[maxn];


struct  AC {
    struct Node {
        int son[26];  // 子结点
		   
        int fail;     // fail 指针
        int du;       // 入度
        int idx;
        int len;
        int cnt=0; 		// 出现位置 / 匹配计数
        int sum=0;
        int ans=0;
        void init() {  // 结点初始化
            memset(son, 0, sizeof(son));
			fail = idx = 0;
			cnt = 0;
			sum = 0;
			ans = 0;
        }
    } tr[SIZE];

    int tot; 
    
	int pidx;

    void init() {
        tot = pidx = 0;
        tr[0].init();
    }

    void insert(const string& s, int idx) {
        int u = 0;
        for (int i = 0; i < (int)s.length(); i++) {
            int& son = tr[u].son[s[i] - 'a'];
            if (!son) son = ++tot, tr[son].init();
            u = son;
        	tr[u].cnt += 1;
        }
        tr[u].idx = idx;
        tr[u].len = s.length();
    }
    

    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++)
            if (tr[0].son[i]) q.push(tr[0].son[i]);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (tr[u].son[i]) {                               // 存在对应子结点
                    tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];  // 只用跳一次 fail 指针
                    tr[tr[tr[u].fail].son[i]].du++;                 // 入度计数
                    q.push(tr[u].son[i]);                           // 并加入队列
                }
                else tr[u].son[i] =tr[tr[u].fail].son[i]; 
                // 将不存在的字典树的状态链接到了失配指针的对应状态
            }
        }
    }

	int ans=0;
    void query(string& t) {
        int u = 0;
        for (int i=0;i<t.length();i++) {
        	char ch=t[i];
            u = tr[u].son[ch - 'a'];
            //tr[u].ans.push_back(i);
			tr[u].ans++;
        }
    }
    void topu() {
        queue<int> q;
        for (int i = 0; i <= tot; i++)
            if (tr[i].du == 0) q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if(tr[u].ans)ans=max(ans,tr[u].sum);
            int v = tr[u].fail;
            tr[v].ans+=tr[u].ans;
            if (!--tr[v].du) q.push(v);
        }
    }
    int qcnt(string& t)
    { 	ans=0;
    	query(t);
        topu();
        return ans;
    }
    int sum=0;
    void dfs(int u){
    //	cout<<u<<"\n";
    	tr[u].sum=sum;
    	for(int i=0;i<26;i++){
    		if(tr[u].son[i]){
    			sum+=tr[tr[u].son[i]].cnt;
    			dfs(tr[u].son[i]);
    			sum-=tr[tr[u].son[i]].cnt;
			}
		}
	}
}pp;
int n,m;
void solve()
{
    cin >> n >> m; 
    cin>>s;
    pp.init();
    
    for(int i=1;i<=m;i++){
    	cin>>t[i];pp.insert(t[i],i);
	}
	pp.sum=0;
	pp.dfs(0);
	pp.build();
	cout<<max(0,pp.qcnt(s))<<"\n";
}
signed main()
{
    int _ = 1;
    cin >> _;
    while (_--)solve(); return 0;
}