Prefix Span: Code

                       /*Bismillahir Rahmanur Rahim*/
//Template created by topcoder00

# include <list>
# include <bitset>
# include <algorithm>
# include <sstream>
# include <iostream>
# include <cstdlib>
# include <ctime>
# include <set>
# include <map>
# include <cmath>
# include <queue>
# include <limits>
# include <stack>
# include <vector>
# include <cstring>
# include <cstdio>
# include <fstream>
using namespace std;

# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)
# define all(c) (c).begin(), (c).end()
# define sz(x) x.size()
# define pb push_back
# define UNQ(s) {sort(all(s));(s).erase(unique(all(s)),s.end());}
# define VS vector<string>

VS mseq;
map<char,int>mpc ;
int min_sup;
int cou=0;
VS prefix;

void count1(string s,VS seq)
{
    for(int k=0;k<sz(s);k++){
    REP(i,sz(seq))
    {
        REP(j,sz(seq[i]))
        {
            if(seq[i][j]==s[k])
            {
                mpc[s[k]]++;break;
            }
        }
    }
    }
}
map<string,int>mpvc;

void count2(VS vs, VS seq)
{
    for(int k=1;k<sz(vs);k++)
    {
        REP(i,sz(seq))
        {
            REP(j,sz(seq[i]))
            {
                if(seq[i].substr(j,sz(vs[k]))==vs[k])
                {
                    if(sz(vs[k])==1&&seq[i][j-1]!='_')
                    {
                        int p=j;
                        while(1)
                        {
                            p--;
                            if(p==0 || seq[i][p]=='_' || seq[i][p]=='(' || seq[i][p]==' ')break;
                        }
                        if(seq[i][p]!='_')
                        {
                            mpvc[vs[k]]++;
                            break;
                        }
                    }
                    else if(sz(vs[k])>1) {mpvc[vs[k]]++;break;}
                }
            }
        }
    }
}
VS fsp;
map<string,bool>mp;

void prin();

void mainkaj(string s)
{
    string ma=s;
    for(int i=0;i<sz(s);i++)
    {
        if(s[i]=='('){s[i]=' ';
           while(s[i]!=')')i++;s[i]=' ';}
        else s.insert(i," "),i++;
    }

    VS pr, projected;
    pr.clear();projected.clear();

    string test="";
    stringstream ss(s);

    while(ss>>test)
    {
        pr.pb(test);
    }
    s.clear();
    for(int i=0;i<sz(pr);i++)s+=pr[i];

    REP(i,sz(mseq))
    {
        int br=0;string proj=""; int k=0;

        REP(j,sz(mseq[i]))
        {
            if(mseq[i].substr(j,sz(pr[k]))==pr[k])
            {
                if(br==1 && k!=(sz(pr)-1))
                {
                    while(mseq[i][j]!=')')j++;br=0;
                }
                else if(br==1 && k==(sz(pr)-1))
                {
                    j+=(sz(pr[k])-1);
                    if(mseq[i][j+1]==')')j+=1;
                    else if(mseq[i][j+1]!=')' && mseq[i][j+1]!=' ')
                        proj.pb('_'),proj.pb(pr[sz(pr)-1][sz(pr[sz(pr)-1])-1]);
                    br=0;
                }
                else if(br==0)j+=1;
                k++;
            }
            if(mseq[i][j]=='(')br=1;

            if(k==sz(pr))
            {
                proj+=mseq[i].substr(j+1);
                bool c=0;
                while(mseq[i][j]!='>'){j++;if(isalpha(mseq[i][j]))c=1;}
                if(c==0)proj.clear();
                break;
            }
        }
        if(sz(proj)>1)projected.pb(proj);
    }

/*    cout<<"Projected Database:"<<endl;
    REP(i,sz(projected))
        cout<<projected[i]<<endl;
*/
    VS frst;frst.clear();

    REP(i,sz(projected))
    {
        string tt="";
        REP(j,sz(projected[i]))
        {
            if(projected[i][j]=='_' && isalpha(projected[i][j+1]))
            {
                if(isalpha(projected[i][j+2]))tt+=projected[i].substr(j+1,j+2);
            }
            else if(isalpha(projected[i][j]))tt.pb(projected[i][j]);
            frst.pb(tt);tt="";
        }
    }

    UNQ(frst); mpvc.clear();count2(frst,projected);

/*    cout<<"Frequency of members\n";
    REP(i,sz(frst))
    {
      if(mpvc[frst[i]]>0)cout<<frst[i]<<" "<<mpvc[frst[i]]<<endl;
    }
*/
    REP(i,sz(frst))
    {
        string fp=ma;

        if(mpvc[frst[i]]>=min_sup)
        {
            if(fp[sz(fp)-1]==frst[i][0] && sz(frst[i])>1)
            {
                fp.erase(sz(fp)-1);
                fp.pb('(');
                fp+=frst[i];
                fp.pb(')');
            }
            else fp+=frst[i];
            fsp.pb(fp);
        }
    }
      prin();
}

void prin()
{
    for(int i=0;i<sz(fsp);i++)
    {
        string t;
        stringstream os(fsp[i]);
        string p="";
        while(os>>t)p+=t;
        if(mp[p]==0 && sz(p)>1)
            cout<<"\n"<<fsp[i]<<endl,mp[p]=1,mainkaj(p);
    }
}

int main()
{

//freopen("prefixspan_in.txt","r",stdin);
freopen("prefixspan_out.txt","w",stdout);

    int br=0;
    string frst;
    while(1)
    {
        string s;
        getline(cin,s);
        if(sz(s)==0)br++;
        if(br==2)break;
        if(sz(s)>1)br=0;

        for(int i=0;i<sz(s);i++)
        {
            if(isalpha(s[i]))frst.pb(s[i]);
            if(s[i]=='<')
            s.insert(i+1," ");
            else if(s[i]=='(')
            {
                while(s[i]!=')'){if(isalpha(s[i]))frst.pb(s[i]);i++;}s.insert(i+1," ");
            }
            else if(s[i]!=' ')s.insert(i+1," ");
        }
        mseq.pb(s);
    }

    cout<<"Mininum support?";cin>>min_sup;

    UNQ(frst);count1(frst,mseq);

    REP(i,sz(frst))
    {
        if(mpc[frst[i]]<min_sup)frst.erase(i);
    }

    REP(i,sz(frst)){string tt;tt.pb(frst[i]);prefix.pb(tt);tt.clear();}
    string line="\n-------------------------------------------------------------\n";
    REP(i,sz(prefix)){cout<<line<<"Prefix of ("<<prefix[i]<<") are below:"<<line;mainkaj(prefix[i]);mpc.clear();}
    cout<<"\n\n\n\n\n\n\n\n\n\nDesigned by Iftekhar ahmed eather,\nStudent of CSE (07 batch),\nBUBT, Mirpur";
    return 0;
}