分析

在trie树上贪心，将所有串加入trie树中，在深度较深的地方匹配会更优。

由于只需要知道最后的总质量，所以直接取每个点的子树中最大的匹配即可

复杂度\(O(\sum len)\)

加串的时候把路径上\(val\)加\(1\)，查询串的时候把沿途\(val\)减\(1\)，\(ans\)为减去的\(1\)的个数。

注意\(val\)为\(0\)的情况，如果后面有\(val\)为大于等于\(1\)的点，那么说明这次查询的串比以前查询的串贡献的答案更优，那么就直接加上后面那些\(val\)大于等于\(1\)的点的个数，而不用撤销操作。因为如此计算相当于自动撤销了之前的次优解。不存在次优解到另一分叉而使此串查询路径上\(val\)为\(0\)的情况，因为如果到另一分叉则此串查询路径上至少加了两个串。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x){

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

struct Trie

{

	static const int SigmaSize=26;

	int index(char c)

	{

		return c-'a';

	}

	int ch[800010][26];

	int val[800010];

	int tcnt;

	void insert(char*s)

	{

		int f=0;

		while(*s)

		{

			int c=index(*s);

			if(!ch[f][c])

				ch[f][c]=++tcnt;

			f=ch[f][c];

//			cerr<<"*s="<<*s<<" f="<<f<<endl;

			++val[f];

			++s;

		}

	}

	int query(char*s)

	{

		int f=0,ans=0;

		while(*s)

		{

			int c=index(*s);

			if(!ch[f][c])

				return ans;

			f=ch[f][c];

			if(val[f]>0)

				++ans,--val[f];

//			else

//				return ans; // edit 2 : 不能直接return，相当于撤销之前的操作

			++s;

		}

		return ans; // edit 1 : 保证完全匹配有返回值

	}

}T;

char s[800010];

int main()

{

//  freopen(".in","r",stdin);

//  freopen(".out","w",stdout);

	int n;

	read(n);

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

	{

		scanf("%s",s);

		T.insert(s);

	}

	int ans=0;

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

	{

		scanf("%s",s);

		ans+=T.query(s);

	}

	printf("%d\n",ans);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}