-
Notifications
You must be signed in to change notification settings - Fork 1
/
bedbathandbeyond.com.cpp
78 lines (53 loc) · 1.72 KB
/
bedbathandbeyond.com.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define ui unsigned int
void print_dp(int n1,int n2, vector< vector<int> > dp){
for(int i=0; i<n1; i++){
for(int j=0; j<n2; j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int fill_dp(string s1, string s2, vector< vector<int> > dp){
for(int i=0; i<s1.length(); i++) if(s1[i]== s2[0]) dp[i][0]=1; else dp[i][0]= 0;
for(int j=0; j<s2.length(); j++) if(s1[0]== s2[j]) dp[0][j]=1; else dp[0][j]= 0;
int maxy=0;
for(int i=1; i<s1.length(); i++){
for(int j=1; j<s2.length(); j++){
if(s1[i]==s2[j]){
dp[i][j]=1+ dp[i-1][j-1];
if (dp[i][j]> maxy) maxy= dp[i][j];
}
else dp[i][j]= 0;
}
}
return maxy;
}
vector<string> find_keywords(const string s, const vector<string> &dic){
ui length1= s.length();
ui length2=0;
for_each(dic.begin(), dic.end(),
[&](string s) {if(length2< s.length()) length2=s.length();});
/*
ui** dp;
dp=(ui**) calloc(length1, sizeof(ui*));
for_each(dp, dp+length1,
[&](ui* i) {i= (ui*) calloc(length2, sizeof(ui));}); */
vector< vector<int> > dp(length1, vector<int>(length2));
vector<string> *ans= new vector<string>;
for(int i=0; i<dic.size(); i++)
if(fill_dp(s, dic[i], dp)== dic[i].length()) ans->push_back(dic[i]);
//delete dp;
return *ans;
}
int main(){
string s; cin>>s;
int dic_length; cin>>dic_length;
vector<string> dic(dic_length);
for(int i=0; i<dic_length; i++) cin>>dic[i];
vector<string> ans= find_keywords(s, dic);
for(int i=0; i<ans.size(); i++) cout<<ans[i]<<" ";
delete &ans;
cout<<endl;
}