传送门：点击打开链接
题意：a串有很多个，然后能把a串剪断，剪成很多条小区间，区间还能翻转。然后给你一个b串，求b串用a串的区间的字符去组合出来，最少需要的区间数，要求输出方案。长度<=2100
思路：首先，我的思路非常蠢。。标准答案是暴力+贪心，确实后来想了下讲的太有道理了~
我的思路是，把a串的所有子串全部取出来，然后双哈希保存。然后再对b串做dp。
如果[j+1,i]在a串中存在，那么就能有dp[i]=max(dp[i],dp[j]+1)，其中j<i，dp[i]表示正在考虑前i个字符
然后再保存dp的选择情况，用DFS沿着选择的路回溯打印方案。
哈希的时候有个问题，字符a不能当作0来看，应该当作1，否则有可能长度不相等的字符串但是哈希的结果完全一模一样~
最后虽然过了，但是在cf上竟跑了800ms，不得不说还是算比较慢了，。
不过还是想说下这双哈希的办法蛮好的，以后遇到字符串的题目都能往双哈希的方向考虑。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 2100 + 5;
const int mod1 = 3199993;
const int mod2 = 1e9 + 7;//3199993 3199991
const int INF = 0x3f3f3f3f;int n, m;
int pre[MX], dp[MX];
char s1[MX], s2[MX];
PII temp[MX][MX], pt[MX];
struct Hash {PII s;int t2, nxt;
} HT[MX * MX];
int Head[mod1], rear;
void Hash_init() {rear = 0;memset(Head, -1, sizeof(Head));
}
void Hash_add(PII h, PII s) {for(int i = Head[h.first]; ~i; i = HT[i].nxt) {if(HT[i].t2 == h.second) return;}HT[rear].t2 = h.second;HT[rear].nxt = Head[h.first];HT[rear].s = s;Head[h.first] = rear++;
}
bool Hash_get(PII h, PII &ret) {for(int i = Head[h.first]; ~i; i = HT[i].nxt) {if(HT[i].t2 == h.second) {ret = HT[i].s;return true;}}return false;
}void presolve() {Hash_init();for(int i = 1; i <= n; i++) {LL cnt1 = 0, cnt2 = 0;for(int j = i; j <= n; j++) {cnt1 = (cnt1 * 26 + s1[j] - 'a' + 1) % mod1;cnt2 = (cnt2 * 26 + s1[j] - 'a' + 1) % mod2;Hash_add(PII(cnt1, cnt2), PII(i, j));}}for(int i = n; i >= 1; i--) {LL cnt1 = 0, cnt2 = 0;for(int j = i; j >= 1; j--) {cnt1 = (cnt1 * 26 + s1[j] - 'a' + 1) % mod1;cnt2 = (cnt2 * 26 + s1[j] - 'a' + 1) % mod2;Hash_add(PII(cnt1, cnt2), PII(i, j));}}
}void DFS(int u) {if(pre[u] == -1) return;DFS(pre[u]);printf("%d %d\n", pt[u].first, pt[u].second);
}void solve() {dp[0] = 0;for(int i = 1; i <= m; i++) {LL cnt1 = 0, cnt2 = 0;for(int j = i; j <= m; j++) {cnt1 = (cnt1 * 26 + s2[j] - 'a' + 1) % mod1;cnt2 = (cnt2 * 26 + s2[j] - 'a' + 1) % mod2;temp[i][j] = PII(cnt1, cnt2);}}for(int i = 1; i <= m; i++) {for(int j = 0; j < i; j++) {PII t = temp[j + 1][i], ret;if(Hash_get(t, ret) && dp[j] + 1 < dp[i]) {dp[i] = dp[j] + 1;pre[i] = j; pt[i] = ret;}}}if(dp[m] == INF) {printf("-1\n"); return;}printf("%d\n", dp[m]);DFS(m);
}int main() {//FIN;while(~scanf("%s%s", s1 + 1, s2 + 1)) {memset(pre, -1, sizeof(pre));memset(dp, INF, sizeof(dp));n = strlen(s1 + 1);m = strlen(s2 + 1);presolve();solve();}return 0;
}