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

2019-11-14 10:13:54

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題意

給定兩個串a(chǎn)、b，要求在b中刪掉一個子串，使得b串成為a串的子序列

題解

從b串左邊開始匹配a串左邊，記錄下來匹配到的位置，知道匹配結(jié)束再從b串右邊開始匹配a串右邊，記錄下來匹配到的位置。。。。。然而這需要開兩個數(shù)組。。。否則就像我一樣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;}

上一篇：神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)簡史（第一部分）：從感知機到BP算法

下一篇：leecode 268. Missing Number