#include<iostream> //poj 2250 Compromise
#include<vector>
#include<string>
using namespace std;
vector<string> v1,v2,res;
int table[105][105],tag[105][105];
int dp(int i,int j)
{
if(i==-1||j==-1)
return 0;
if(table[i][j]!=-1)
return table[i][j];
else if(v1[i]==v2[j])
tag[i][j]=0,table[i][j]=dp(i-1,j-1)+1;
else
{
int a=dp(i-1,j),b=dp(i,j-1);
tag[i][j]=a>b?1:2; //tag數組記錄路徑
table[i][j]=max(a,b);
}
return table[i][j];
}
void lcs(int i,int j)
{
if(i==-1||j==-1)
return ;
if(tag[i][j]==0)
res.push_back(v1[i]),lcs(i-1,j-1);
else if(tag[i][j]==1)
lcs(i-1,j);
else
lcs(i,j-1);
}
int main()
{
string str;
while(cin>>str)
{
v1.clear();v2.clear();
res.clear();
memset(table,-1,sizeof(table));
memset(tag,-1,sizeof(tag));
v1.push_back(str);
while(cin>>str&&str!="#")
v1.push_back(str);
while(cin>>str&&str!="#")
v2.push_back(str);
dp(v1.size()-1,v2.size()-1);
lcs(v1.size()-1,v2.size()-1);
for(int i=res.size()-1;i>=0;--i)
cout<<res[i]<<" ";
cout<<endl;
}
return 0;
}
//sicily 1197. Hotel
#include<iostream> //DP,含通用符的字元串的最長比對
#include<string>
#include<cstring>
using namespace std;
string str[10010];
int f[60][60]; //f[i][j]=1,表示一個字元串的0-i子串與另一個字元串的0-j子串比對,f[i][j]=0則是不比對
int dp(int i,int j,int id) //傳回f[i][j],表示字元串str[0][0-i]與字元串str[id][0-j]是否比對
{
if(i==-1&&j==-1) //i=-1,j=-1說明兩個字元串都已搜尋完畢,是以傳回真
return 1;
else if(i==-1) //i=-1,j!=-1,元字元串str[0]已搜尋完畢,但str[id]還未周遊完,是以傳回0
return 0;
else if(j==-1) //i!=-1,j=-1
{
if(str[0][i]=='*')
return dp(i-1,j,id); //當j=-1,如果str[0][i]是'*',我們可以把'*'當作空字元而跳過,繼續往下搜尋
else
return 0;
}
if(f[i][j]!=-1)
return f[i][j]; //記憶化搜尋
if(str[0][i]==str[id][j]||str[0][i]=='?') //兩個字元相同
f[i][j]=dp(i-1,j-1,id);
else if(str[0][i]=='*')
{
int a=dp(i-1,j,id),b=dp(i-1,j-1,id),c=dp(i,j-1,id); //這是重點, a,b,c分别表示'*'當作空字元,一個字母,和一個以上的字母
f[i][j]=max(a,max(b,c));
}
else
f[i][j]=0; //兩個字元不相同,str[0][0-i]與字元串str[id][0-j]肯定無法比對,是以傳回 0
return f[i][j];
}
int main()
{
int n;
while(cin>>str[0]) //str[0]是元字元串
{
int ed=str[0].size()-1;
int s=0;
cin>>n;
for(int i=1;i<=n;++i) //str[1-n]是待比對字元串
{
cin>>str[i];
int ed_i=str[i].size()-1;
memset(f,-1,sizeof(f)); //初始化為-1
if(dp(ed,ed_i,i)==1)
s++;
}
cout<<s<<endl;
}
return 0;
}
