Cod sursa(job #2278303)

Utilizator BRIOI19Ben Test BRIOI19 Data 7 noiembrie 2018 16:53:50
Problema Subsir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#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;
}