[Educational Codeforces Round 17 C (762C)] Two strings

2019-11-14 10:13:54

字体：大中小

来源：转载

供稿：网友

题意

给定两个串a、b，要求在b中删掉一个子串，使得b串成为a串的子序列

题解

从b串左边开始匹配a串左边，记录下来匹配到的位置，知道匹配结束再从b串右边开始匹配a串右边，记录下来匹配到的位置。。。。。然而这需要开两个数组。。。否则就像我一样gg了

代码

/// by ztx// blog.csdn.net/hzoi_ztx#define maxl 100010LLchar s1[maxl], s2[maxl];int posl[maxl] = {0}, posr[maxl] = {0}, m, n, l, r, i, j, ansl, ansr;int main() { scanf("%s%s", s1+1, s2+1); m = strlen(s1+1), n = strlen(s2+1); for (l = j = 1; l <= n; l ++ ) { for ( ; j <= m && !posl[l]; j ++ ) if (s1[j] == s2[l]) posl[l] = j; if (!posl[l]) break; } for (r = n, j = m; r; r -- ) { for ( ; j && !posr[r]; j -- ) if (s1[j] == s2[r]) posr[r] = j; if (!posr[r]) break; } if (l == 1 && r == n) puts("-"); else if (l == 1) puts(s2+r+1); else if (r == n) s2[l] = '/0', puts(s2+1); else if (l == n+1) puts(s2+1); else { if (l-1 > n-r) ansl = l-1, ansr = n+1; else ansl = 0, ansr = r+1; j = r+1; for (i = 1; i < l; i ++ ) { while (j<=n && posr[j]<=posl[i]) j ++ ; if (j > n) break; if (i+n-j+1 > ansl+n-ansr+1) ansl = i, ansr = j; } for (i = 1; i <= ansl; i ++ ) putchar(s2[i]); for (i = ansr; i <= n; i ++ ) putchar(s2[i]); puts(""); } getchar(),getchar(); return 0;}

上一篇：神经网络和深度学习简史（第一部分）：从感知机到BP算法

下一篇：leecode 268. Missing Number