matching_70 pct

#include <bits/stdc++.h>
#define maxN 16
#define maxLen 505
using namespace std;
long long fact[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000}; /// 0!, 1!, 2!, 3!,..., 15!
char a[maxN][maxLen]; /// Primul set de siruri (S1)
char b[maxN][maxLen]; /// Al doilea set de siruri (S2)
int n,i,j,pi[maxLen];
int lena[maxN],lenb[maxN]; /// Lungimile sirurilor din primul set (S1) si al doilea set (S2)
vector<int> v[maxN];
long long dp[maxN][1<<15]; /// Matricea pentru dinamica

bool findMatch(int x,int y) /// Cauta potrivirea
{
    int L=lenb[y];
    int k=0;
    for(int i=1;i<=L;++i)
    {
        while(k>0&&b[y][i]!=a[x][k+1])
            k=pi[k];
        if(b[y][i]==a[x][k+1])
            ++k;
        if(k==lena[x])
            return true;
    }
    return false;
}

int main()
{
    ifstream f("matching.in");
    ofstream g("matching.out");
    f>>n;
    int maxC=(1<<n); /// 2^n

    for(int i=1;i<=n;++i) /// Citesc seturile de siruri S1 si S2
        f>>(a[i]+1)>>(b[i]+1),lena[i]=strlen(a[i]+1),lenb[i]=strlen(b[i]+1);

    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            if(findMatch(i,j))
                v[i].push_back(j-1);
    }

    for(int i=0;i<=n;++i) /// initializez dinamica
        dp[i][0]=1;

    for(int i=1;i<=n;++i) /// Calculez dinamica
        for(int mask=0;mask<maxC;++mask)
        {
            dp[i][mask]+=dp[i-1][mask];
            for(vector<int>::iterator it=v[i].begin();it!=v[i].end();++it)
                if(mask&(1<<(*it)))
                    dp[i][mask]+=dp[i-1][mask^(1<<(*it))];
        }

    g<<fact[n]-dp[n][maxC-1];
    return 0;
}