matching

#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,1LL*479001600,1LL*6227020800,1LL*87178291200,1LL*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)
char c[1030];
int n,i,j,pi[1030];
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
{
    for(int i=2;i<=y;++i)
    {
        pi[i] = pi[i-1];
        while(pi[i]>0&&c[i]!=c[pi[i]+1])
            pi[i]=pi[pi[i]];
        if(c[i]==c[pi[i]+1])
            ++pi[i];
        if(pi[i]==x)
            return true;
    }
    return false;
}

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

    for(int i=1;i<=n;++i)
        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)
        {
            strcpy(c+1, a[i]+1);
            int l1 = strlen(c+1);
            c[l1+1] = '&';
            strcpy(c+2+l1, b[j]+1);
            int l2 = strlen(c+1);
            if(findMatch(l1,l2))
                v[i].push_back(j-1);
        }
    }

    dp[0][0] = 1;

    for(int i=1;i<=n;++i) /// Calculez dinamica
        for(int mask=0;mask<maxC;++mask)
        {
            if (i == __builtin_popcount(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<<1LL*(fact[n]-dp[n][maxC-1]);
    return 0;
}