Pagini recente » Cod sursa (job #2318199) | Cod sursa (job #484415) | Cod sursa (job #1306582) | Cod sursa (job #1633087) | Cod sursa (job #2278303)
#include <iostream>
#include <fstream>
#include <map>
using namespace std;
map<string,int> m1;
int n;
int m;
struct node{
node *arr[27];
int curr;
int count;
};
int ans = 0;
node *newnode(){
node *temp = new node;
temp->curr = 0;
temp->count = 0;
for(int i=0;i<=26;i++){
temp->arr[i] = NULL;
}
return temp;
}
void insert(node *root, string s, int curr){
node *temp = root;
if(s.length()==1){
if(temp->curr!=curr){
temp->curr = curr;
temp->count++;
//std::cout<<s<<endl;
if(temp->count == n){
ans++;
// std::cout<<s<<endl;
}
}
return;
}
for(int i=0;i<s.length();i++){
int verytemp = s[i]-'a';
// std::cout<<verytemp<<" ";
if(temp->curr!=curr){
// std::cout<<temp->curr<<" "<<curr<<endl;
temp->curr = curr;
//std::cout<<temp->curr<<" "<<curr<<endl;
temp->count++;
//std::cout<<temp->count<<endl;
if(temp->count == n){
// std::cout<<s<<endl;
ans++;
}
}
if(temp->arr[verytemp] == NULL){
//std::cout<<verytemp<<" branch"<<endl;
temp->arr[verytemp] = newnode();
}else{
//std::cout<<verytemp<<" not branch"<<endl;
}
temp = temp->arr[verytemp];
}
if(temp->curr!=curr){
temp->curr = curr;
temp->count++;
//std::cout<<temp->count<<endl;
if(temp->count == n){
ans++;
// std::cout<<s<<endl;
}
}
//std::cout<<s<<endl;
}
void check(node *root,string s,int curr){
node *temp = root;
string tempstring = "";
for(int i=0;i<s.length();i++){
int verytemp = s[i]-'a';
if(temp->count >= n && m1[tempstring] == 0){
ans--;
m1[tempstring]++;
// std::cout<<s<<endl;
}
tempstring+=s[i];
if(temp->count < n){
return;
}
if(temp->arr[verytemp] == NULL){
return;
}
temp = temp->arr[verytemp];
}
if(temp->count == n && m1[tempstring] == 0){
ans--;
m1[tempstring]++;
}
}
int main(){
ifstream fin("sub.in");
ofstream fout("sub.out");
fin>>n;
node *root = newnode();
for(int i=1;i<=n;i++){
string s;
fin>>s;
int l =s.length()+1;
int start = -1;
while(l--){
start++;
string hold = s.substr(start,l);
if(l==0||start>=s.length()){
break;
}
insert(root,hold,i);
}
}
fin>>m;
for(int i=0;i<m;i++){
string s;
fin>>s;
int l =s.length()+1;
int start = -1;
while(l--){
start++;
string hold = s.substr(start,l);
if(l==0||start>=s.length()){
break;
}
//std::cout<<hold<<endl;
check(root,hold,i);
}
}
fout<<ans<<endl;
}