题目大概说给两个串，问最少要用多少个第一个串的子串（可以翻转）拼成第二个串。
UVa1401，一个道理。。dp[i]表示前缀i拼接成功所需最少的子串，利用第一个串所有子串建立的Trie树往前枚举转移。
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAXN 2222*2000 int tn,ch[MAXN][],from[MAXN],to[MAXN]; char T[],S[];
int d[],rec[];
void pnt(int x){
if(x<=) return;
pnt(x-abs(from[rec[x]]-to[rec[x]])-);
printf("%d %d\n",to[rec[x]],from[rec[x]]);
}
int main(){
scanf("%s%s",T+,S+);
int i;
for(i=; T[i]; ++i){
int x=;
for(int j=i; T[j]; ++j){
int y=T[j]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
from[x]=i; to[x]=j;
}
}
for(--i; i>=; --i){
int x=;
for(int j=i; j>=; --j){
int y=T[j]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
from[x]=i; to[x]=j;
}
}
rec[]=;
for(i=; S[i]; ++i){
int x=;
for(int j=i; j>=; --j){
int y=S[j]-'a';
if(ch[x][y]==) break;
x=ch[x][y];
if(rec[j-]){
if(d[i]== || d[i]>d[j-]+){
d[i]=d[j-]+;
rec[i]=x;
}
}
}
}
if(d[i-]==){
printf("-1");
return ;
}
printf("%d\n",d[i-]);
pnt(i-);
return ;
}