首页 > 代码库 > Codeforces Round #422 (Div. 2) E. Liar 后缀数组+RMQ+DP
Codeforces Round #422 (Div. 2) E. Liar 后缀数组+RMQ+DP
The first semester ended. You know, after the end of the first semester the holidays begin. On holidays Noora decided to return to Vi?kopolis. As a modest souvenir for Leha, she brought a sausage of length m from Pavlopolis. Everyone knows that any sausage can be represented as a string of lowercase English letters, the length of which is equal to the length of the sausage.
Leha was very pleased with the gift and immediately ate the sausage. But then he realized that it was a quite tactless act, because the sausage was a souvenir! So the hacker immediately went to the butcher shop. Unfortunately, there was only another sausage of length nin the shop. However Leha was not upset and bought this sausage. After coming home, he decided to cut the purchased sausage into several pieces and number the pieces starting from 1 from left to right. Then he wants to select several pieces and glue them together so that the obtained sausage is equal to the sausage that Noora gave. But the hacker can glue two pieces together only when the number of the left piece is less than the number of the right piece. Besides he knows that if he glues more than x pieces, Noora will notice that he has falsified souvenir sausage and will be very upset. Of course Leha doesn’t want to upset the girl. The hacker asks you to find out whether he is able to cut the sausage he bought, and then glue some of the pieces so that Noora doesn‘t notice anything.
Formally, you are given two strings s and t. The length of the string s is n, the length of the string t is m. It is required to select several pairwise non-intersecting substrings from s, so that their concatenation in the same order as these substrings appear in s, is equal to the string t. Denote by f(s, t) the minimal number of substrings to be chosen so that their concatenation is equal to the string t. If it is impossible to choose such substrings, then f(s, t) = ∞. Leha really wants to know whether it’s true that f(s, t) ≤ x.
The first line contains single integer n (1 ≤ n ≤ 105) — length of sausage bought by Leha, i.e. the length of the string s.
The second line contains string s of the length n consisting of lowercase English letters.
The third line contains single integer m (1 ≤ m ≤ n) — length of sausage bought by Noora, i.e. the length of the string t.
The fourth line contains string t of the length m consisting of lowercase English letters.
The fifth line contains single integer x (1 ≤ x ≤ 30) — the maximum number of pieces of sausage that Leha can glue so that Noora doesn’t notice anything.
In the only line print "YES" (without quotes), if Leha is able to succeed in creating new sausage so that Noora doesn‘t notice anything. Otherwise print "NO" (without quotes).
9
hloyaygrt
6
loyyrt
3
YES
Let‘s consider the first sample.
In the optimal answer, Leha should cut the sausage he bought in the following way: hloyaygrt = h + loy + a + y + g + rt. Then he numbers received parts from 1 to 6:
- h — number 1
- loy — number 2
- a — number 3
- y — number 4
- g — number 5
- rt — number 6
Hereupon the hacker should glue the parts with numbers 2, 4 and 6 and get sausage loyygrt equal to one that is given by Noora. Thus, he will have to glue three pieces. Since x = 3 you should print "YES" (without quotes).
In the second sample both sausages coincide with sausages from the first sample. However since x = 2 you should print "NO" (without quotes).
题意：
给你两个字符串，S,T
你可以将S分成任意块编号，至多选出X块编号递增的顺序组成新的串
问你是否能组成T串
题解：
很久没做后缀数组的题了，回顾了下
设定dp[i][j]，表示 0~(i-1)之前 挑选了j块 到达的最大位置
那么对于S串的 i 位置，和T串的dp[i][j] + 1这个位置开始，最长公共前缀是多少？
假设为t ， 那么转移就是 dp[i + t][j+1] = max(dp[i + t][j+1] , dp[i][j] + t);
我们用后缀数组预处理出来lcp，那么查询的时候直接利用RMQ的O(1) 查询就好了
整体复杂度O(nlogn + n*30)
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 5e5+5, M = 1e3+20,inf = 2e9+10;int *ran,r[N],sa[N],height[N],wa[N],wb[N],wm[N];bool cmp(int *r,int a,int b,int l) { return r[a] == r[b] && r[a+l] == r[b+l];}void SA(int *r,int *sa,int n,int m) { int *x=wa,*y=wb,*t; for(int i=0;i<m;++i)wm[i]=0; for(int i=0;i<n;++i)wm[x[i]=r[i]]++; for(int i=1;i<m;++i)wm[i]+=wm[i-1]; for(int i=n-1;i>=0;--i)sa[--wm[x[i]]]=i; for(int i=0,j=1,p=0;p<n;j=j*2,m=p){ for(p=0,i=n-j;i<n;++i)y[p++]=i; for(i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j; for(i=0;i<m;++i)wm[i]=0; for(i=0;i<n;++i)wm[x[y[i]]]++; for(i=1;i<m;++i)wm[i]+=wm[i-1]; for(i=n-1;i>=0;--i)sa[--wm[x[y[i]]]]=y[i]; for(t=x,x=y,y=t,i=p=1,x[sa[0]]=0;i<n;++i) { x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++; } } ran=x;}void Height(int *r,int *sa,int n) { for(int i=0,j=0,k=0;i<n;height[ran[i++]]=k) for(k?--k:0,j=sa[ran[i]-1];r[i+k] == r[j+k];++k);}int dp[N][30];int n,m,f[N][33];char s[N],t[N];void Lcp_init() { for(int i = 1; i <= n+m+1; ++i) dp[i][0] = height[i]; for(int j = 1; (1<<j) <= n + m + 1; ++j) { for(int i = 1; i + (1<<j) - 1 <= n+m-1; ++i) { dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } }}int lcp(int l,int r) { l = ran[l], r = ran[r]; if(l > r) swap(l,r); ++l; int len = r - l + 1; int k = 0; while((1<<(k+1)) <= len) ++k; return min(dp[l][k], dp[r - (1<<k) + 1][k]);}int main() { scanf("%d%s%d%s",&n,s,&m,t); for(int i = 0; i < n; ++i) r[i] = s[i] - ‘a‘ + 1; r[n] = ‘*‘; for(int i = n+1; i < m+n+1; ++i) r[i] = t[i - n - 1] - ‘a‘ + 1; r[n+m+1] = 0; SA(r,sa,n+m+1+1,256); Height(r,sa,n+m+1); Lcp_init(); int X; scanf("%d",&X); int mx = 0; for(int i = 0; i <= n; ++i) { for(int j = 0; j <= X; ++j) { f[i+1][j] = max(f[i+1][j],f[i][j]); int t = lcp(i,f[i][j] + n + 1); f[i + t][j+1] = max(f[i + t][j+1] , f[i][j] + t); mx = max(f[i][j],mx); } } if(mx == m) puts("YES"); else puts("NO"); return 0;}
Codeforces Round #422 (Div. 2) E. Liar 后缀数组+RMQ+DP