Description：

给 $n$ 个模板串，和一个文本串，每次找到在文本串中出现最早的模板串删掉，问最后文本串剩什么。

$1\leqslant \sum l\leqslant10^5$

Solution：

与[bzoj3942][http://localhost:4000/2018/09/14/bzoj3942/]类似的做法，只不过从一个串扩展到了多个串，那就建出 $AC$ 自动机，在每个模板串结束点上记录长度，然后把文本串在上面跑，同时维护一个栈表示还剩什么，如果找到一个位置就弹长度那么多次栈即可，因为是找到的第一个模板串所以一定不会出现需要重复好几次上述操作的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXL 100010

char s[MAXL];

char c[MAXL];

int n;

struct node

{

	int tr[26];

	int fail;

	int len;

	node(){len = 0;}

}t[MAXL];

int ptr = 0;

int newnode(){return ++ptr;}

int root = 0;

void insert(char c[])

{

	int cur = root;

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - 'a'] == 0)

			t[cur].tr[c[i] - 'a'] = newnode();

		cur = t[cur].tr[c[i] - 'a'];

	}

	t[cur].len = l;

	return;

}

void make_fail()

{

	queue<int> q;

	for(int i = 0;i < 26;++i)

		if(t[root].tr[i] != 0)

			q.push(t[root].tr[i]);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = 0;i < 26;++i)

		{

			if(t[k].tr[i] != 0)

			{

				t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

				q.push(t[k].tr[i]);

			}

			else t[k].tr[i] = t[t[k].fail].tr[i];

		}

	}

	return;

}

int stack[MAXL],top = 0;

int pos[MAXL];

int main()

{

	scanf("%s",s + 1);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",c + 1);

		insert(c);

	}

	make_fail();

	int l = strlen(s + 1);

	int cur = root;

	for(int i = 1;i <= l;++i)

	{

		cur = t[cur].tr[s[i] - 'a'];

		pos[i] = cur;

		stack[++top] = i;

		if(t[cur].len != 0)

		{

			for(int k = 1;k <= t[cur].len;++k)--top;

			cur = pos[stack[top]];

		}	

	}

	for(int k = 1;k <= top;++k)cout << s[stack[k]];cout << endl;

	return 0;

}