Hackerrank11 LCS Returns 枚举+LCS

时间：2021-01-16 07:26:20

Given two strings,  a and , b find and print the total number of ways to insert a character at any position in string a such that the length of the Longest Common Subsequence of characters in the two strings increases by one.

Input Format

The first line contains a single string denoting a. 
The second line contains a single string denoting b.

Constraints

Scoring

  • Strings a and b are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
  • The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).

　　1<=|a|<=5000      1<=|b|<=5000

Output Format

Print a single integer denoting the total number of ways to insert a character into string  in such a way that the length of the longest common subsequence of  and  increases by one.

Sample Input

aa

baaa

Sample Output

4

题意：给出两个串a b，由字母或数字组成， 然后在a串任意一个位置插入一个字母或数字， 使得ab串的LCS增加1  求方案数
思路：枚举a串的n+1个插入位置i，枚举每种插入的字符c，对于每个c，在b中找到对应的位置j， 如果LCS[i-1][j-1] + LCS2[i+1][j+1] == K(ab串原来的lcs) 那么就可以通过在i位置插入字符c来满足条件， 其中Lcs【i】【j】表示a串的1-i与b串的1-j之间的lcs  Lcs2【i】【j】表示a串的i-la与b串的j-lb之间的lcs    lcs[i][j]求法就是普通的做法，lcs2[i][j]逆过来再求一遍就好了


#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

#include <string>

#include <stack>

#include <cmath>

#include <cstdlib>

#include <iostream>

#include <map>

#include <set>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long ll;

const int N = ;

char a[N], b[N], ra[N], rb[N];

int dp1[N][N], dp2[N][N];

int la, lb, K;

void init1() {

    memset(dp1, , sizeof dp1);

    for(int i = ; i <= la; ++i)

        for(int j = ; j <= lb; ++j) {

            if(a[i - ] == b[j - ]) dp1[i][j] = dp1[i - ][j - ] + ;

            else dp1[i][j] = max(dp1[i - ][j], dp1[i][j - ]);

    }

    K = dp1[la][lb];

}

void init2() {

    memset(dp2, , sizeof dp2);

    int l = ;

    for(int i = la - ; i >= ; --i) ra[l++] = a[i];

    l = ;

    for(int i = lb - ; i >= ; --i) rb[l++] = b[i];

    for(int i = ; i <= la; ++i)

        for(int j = ; j <= lb; ++j) {

            if(ra[i - ] == rb[j - ]) dp2[i][j] = dp2[i - ][j - ] + ;

            else dp2[i][j] = max(dp2[i - ][j], dp2[i][j - ]);

    }

}

vector<int> p[];

vector<char> alp;

void solve() {

    for(int i = ; i < ; ++i) p[i].clear();

    for(int i = ; i < lb; ++i) p[ b[i] ].push_back(i + );

    alp.clear();

    for(char i = 'a'; i <= 'z'; ++i) alp.push_back(i);

    for(char i = 'A'; i <= 'Z'; ++i) alp.push_back(i);

    for(char i = ''; i <= ''; ++i) alp.push_back(i);

    int ans = ;

    for(int i = ; i <= la + ; ++i) {

        for(int j = ; j < alp.size(); ++j) {

            char c = alp[j];

            for(int k = ; k < p[c].size(); ++k) {

                int r1 = i - ;

                int r2 = la - i + ;

                int r3 = p[c][k] - ;

                int r4 = lb - p[c][k];

                if(dp1[r1][r3] + dp2[r2][r4] == K) { ans++; break; }

            }

        }

    }

    printf("%d\n", ans);

}

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

#endif

    while(~scanf("%s%s", a, b)) {

        la = strlen(a);

        lb = strlen(b);

        init1();

        init2();

        solve();

    }

    return ;

}
 

相关文章