Find the number of common subsequences of K strings

eg

Carelessness ：

Find the number of common substrings of three strings

Ideas ：
First, the sequence automata is used to find the next Array .

void init(char* s,ll mas[][30])
{
	ll len=strlen(s+1);
	for(int i=len;i;--i)
	{
		for(int j=0;j<26;++j) mas[i-1][j]=mas[i][j];
		
		mas[i-1][s[i]-'a']=i;
	}
}

hypothesis dp【i】【j】【k】 Express a Serial number i After characters ,b Serial number j After characters ,c Serial number k Number of common substrings after characters ,

Then enumerate the number of substrings starting with each character , Recursion is enough .

Because the same character is also the same substring , therefore

if(x&&y&&z) dp[x][y][z]++;

code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=110;
char a[N],b[N],c[N];
ll nea[N][30],neb[N][30],nec[N][30];
void init(char* s,ll mas[][30])
{
	ll len=strlen(s+1);
	for(int i=len;i;--i)
	{
		for(int j=0;j<26;++j) mas[i-1][j]=mas[i][j];
		
		mas[i-1][s[i]-'a']=i;
	}
}
ll dp[N][N][N];
ll dfs(ll x,ll y,ll z)
{
	if(dp[x][y][z]) return dp[x][y][z];
	for(int i=0;i<26;++i)
	{
		if(nea[x][i]&&neb[y][i]&&nec[z][i])
		{
			dp[x][y][z]+=dfs(nea[x][i],neb[y][i],nec[z][i]);
		}
	}
	if(x&&y&&z) dp[x][y][z]++;
	return dp[x][y][z];
}
int main()
{
	cin>>(a+1);cin>>(b+1);cin>>(c+1);
	init(a,nea);init(b,neb);init(c,nec);
	cout<<dfs(0,0,0)<<endl;
	return 0;
 } 

The same is true for multiple strings . 

in addition , Using sequential automata to judge whether it is a substring ：

Cattle guest

Just cover the board directly

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+1000;
ll n;
char s[N];char ss[N];
ll ne[N][30];
void init()
{
	ll len=strlen(s+1);
	for(int i=len;i;--i)
	{
		for(int j=0;j<26;++j) ne[i-1][j]=ne[i][j];
	    ne[i-1][s[i]-'a']=i;
	}
}
void solve()
{
	cin>>(ss+1);
	ll p=0;
	for(int i=1;i<=strlen(ss+1);++i)
	{
		p=ne[p][ss[i]-'a'];
		if(!p)
		{
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
}
int main()
{
	cin>>(s+1);
	cin>>n;
	init();
	while(n--)
	{
		solve();
	}
	return 0;
}

Water is healthier ~