D. Huge Strings Codeforces Round #438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)

http://codeforces.com/contest/868/problem/D

优化：两个串合并

原有状态+ 第一个串的尾部&第二个串的头部的状态

串变为第一个串的头部&第二个串的尾部

注意：

头尾不能重复

如串A合并串A

这就意味着串的头尾不能有重合，

详见代码

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <time.h>

#include <string>

#include <set>

#include <map>

#include <list>

#include <stack>

#include <queue>

#include <vector>

#include <bitset>

#include <ext/rope>

#include <algorithm>

#include <iostream>

using namespace std;

#define ll long long

#define minv 1e-6

#define inf 1e9

#define pi 3.1415926536

#define E  2.7182818284

const ll mod=1e9+;//

const int maxn=;

int w=;

int f[maxn][<<(+)]={},add[+];

int len,value;

string str,s,pre[maxn],post[maxn];

void work(int index,string a)

{

    int i,j,z;

    len=a.length();

    for (j=;j<=w;j++)

    {

        value=;

        z=(<<(j-))-;

        for (i=;i<len;i++)

        {

            value=(value<<|(a[i]==''));

            if (i>=j-)

            {

                f[index][value+add[j]]=;

                value=value&z;

            }

        }

    }

}

int main()

{

    int n,q,Q,x,y,i;

    add[]=;

    for (i=;i<=w+;i++)

        add[i]=(<<i)-;

    scanf("%d",&n);

    for (i=;i<=n;i++)

    {

        cin>>str;

        work(i,str);

        len=str.size();

        if (len<=w)

            pre[i]=str;

        else

        {

            pre[i]=str.substr(,w);

            if (len>=w+w)

                post[i]=str.substr(str.length()-w,w);

            else

                post[i]=str.substr(str.length()-len+w,len-w);

        }

    }

    scanf("%d",&q);

    for (Q=n+;Q<=n+q;Q++)

    {

        scanf("%d%d",&x,&y);

        for (i=;i<add[w+];i++)

            f[Q][i]=f[x][i] | f[y][i];

        if (post[x].empty())

            str=pre[x];

        else if (post[x].length()<w)

            str=pre[x].substr(pre[x].length()-(w-post[x].length()),w-post[x].length())+post[x];

        else

            str=post[x];

        str+=pre[y];

        work(Q,str);

        str=pre[x]+post[x]+pre[y]+post[y];

        pre[Q]=str.substr(,min(w,(int)str.length()));

        str.erase(,min(w,(int)str.length()));

        post[Q]=str.substr(str.length()-min(w,(int)str.length()),min(w,(int)str.length()));

        for (i=;i<add[w+];i++)

            if (f[Q][i]==)

                break;

        printf("%d\n",(int)(log(+i+minv)/log())-);

    }

    return ;

}