C++11(clang++ 3.9) 解法, 执行用时: 20ms, 内存消耗: 2280K, 提交时间: 2020-03-24 21:53:51

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


const int N=1000;
char s1[N],s2[N],s3[N]; 

int MSK;

int t[N<<1][53],fa[N<<1],ed[N<<1],cnt=0;

void insert(char *s,int id)
{
	int p=0;
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int c;
		if(s[i]>='A'&&s[i]<='Z')  c=s[i]-'A';
		else c=s[i]-'a'+26;
		if(t[p][c]==0) t[p][c]=++cnt;
		p=t[p][c];
	}
	ed[p]|=1<<id;//进制压位 
}

void build()
{
	queue<int>q;
	for(int i=0;i<52;i++) if(t[0][i]) q.push(t[0][i]);
	while(q.size())
	{
		int tmp=q.front();
		q.pop();
		ed[tmp]|=ed[fa[tmp]];
		for(int i=0;i<52;i++)
		{
			if(t[tmp][i])
			{
				fa[t[tmp][i]]=t[fa[tmp]][i];
				q.push(t[tmp][i]);
			}
			else t[tmp][i]=t[fa[tmp]][i];
		}
	}
} 

int nxt[2][N][60];
void getnxt(char *s,int tp)//序列自动机  
{
	int len=strlen(s+1); 
	for(int i=len;i>=1;i--)
	{
		for(int j=0;j<52;j++) nxt[tp][i-1][j]=nxt[tp][i][j];
		int c;
		if(s[i]>='A'&&s[i]<='Z')  c=s[i]-'A';
		else c=s[i]-'a'+26;
		nxt[tp][i-1][c]=i;
	}
}

struct node
{
	int x,y,now,s;
	bool operator<(const node &M) const
	{
		if(x==M.x) 
		{
			if(y==M.y)
			{
				if(now==M.now) return s<M.s;
				return now<M.now;
			}
			return y<M.y ;
		}
		return x<M.x;
	} 
};
map<node,int>dp;
int g[N][N];
int dfs(int x,int y,int now,int s)//s1串的下标 ，s2串的下标 ，ac自动机节点 ，集合情况 
{
	node tmp; tmp.x=x,tmp.y=y,tmp.now=now,tmp.s=s;
	if(s==MSK) return dp[tmp]=g[x][y]+1;
	int ans=dp[tmp];
	if(ans) return ans;
	for(int i=0;i<=52;i++)
	{
		if(nxt[0][x][i]&&nxt[1][y][i])
		  ans=max(ans,dfs(nxt[0][x][i],nxt[1][y][i],t[now][i],s|ed[t[now][i]]));
	}
	if(ans==0||ans==-1) return dp[tmp]=-1;
	return dp[tmp]=ans+1;
} 
int main()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=k;i++)
	{
		int x;
		scanf("%d",&x);
	}
	scanf("%s%s",s1+1,s2+1);
	for(int i=0;i<k;i++)
	{
		scanf("%s",&s3);
		insert(s3,i);
	}
	build();MSK=(1<<k)-1;
	getnxt(s1,0);getnxt(s2,1);
	for(int i=n;i>=1;i--)//预处理后面个lCS 
	{
		for(int j=m;j>=1;j--)
		{
			if(s1[i]==s2[j]) g[i][j]=max(g[i][j],g[i+1][j+1]+1);
			else g[i][j]=max(g[i+1][j],g[i][j+1]);
		}
	}
	int ans = dfs(0,0,0,0)-2;
    printf("%d\n",max(ans,0));
	return 0;
}