POJ2004 Mix and Build

良問だと思う。文字列の長さをL,文字列数をNとすると,O(N L^2 log N).
TLEぎりぎりでAC.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef pair<string,int>psi;
typedef pair<int,psi>pisi;
int len[10000];
int frm[10000];
int main()
{
	vector<string>zvec;
	vector<pisi>vec;
	for(int i=0;;i++)
	{
		string zan;
		if(!(cin>>zan))
		{
			break;
		}
		zvec.push_back(zan);
		sort(zan.begin(),zan.end());
		vec.push_back(make_pair(zan.size(),make_pair(zan,i)));
	}
	sort(vec.begin(),vec.end());
	int maxi=0,nn;
	for(int i=0;i<vec.size();i++)
	{
		frm[i]=i;
		len[i]=0;
		for(int j=0;j<vec[i].second.first.size();j++)
		{
			string subs=vec[i].second.first.substr(0,j)+vec[i].second.first.substr(j+1);
			int low=lower_bound(vec.begin(),vec.begin()+i,make_pair(int(vec[i].second.first.size())-1,make_pair(subs,0)))-vec.begin();
			if(vec[low].second.first==subs)
			{
				if(len[i]<len[low]+1)
				{
					len[i]=len[low]+1;
					frm[i]=low;
				}
			}
		}
		if(len[i]>maxi)
		{
			maxi=len[i];
			nn=i;
		}
	}
	vector<int>ans;
	for(;;)
	{
		ans.push_back(nn);
		if(frm[nn]==nn)
		{
			break;
		}
		nn=frm[nn];
	}
	reverse(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++)
	{
		cout<<zvec[vec[ans[i]].second.second]<<endl;
	}
}