Hackerrank11 LCS Returns 枚举+LCS

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 = 5005;

char a[N], b[N], ra[N], rb[N];
int dp1[N][N], dp2[N][N];
int la, lb, K;
void init1() {
    memset(dp1, 0, sizeof dp1);
    for(int i = 1; i <= la; ++i)
        for(int j = 1; j <= lb; ++j) {
            if(a[i - 1] == b[j - 1]) dp1[i][j] = dp1[i - 1][j - 1] + 1;
            else dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]);
    }
    K = dp1[la][lb];
}
void init2() {
    memset(dp2, 0, sizeof dp2);
    int l = 0;
    for(int i = la - 1; i >= 0; --i) ra[l++] = a[i];
    l = 0;
    for(int i = lb - 1; i >= 0; --i) rb[l++] = b[i];
    for(int i = 1; i <= la; ++i)
        for(int j = 1; j <= lb; ++j) {
            if(ra[i - 1] == rb[j - 1]) dp2[i][j] = dp2[i - 1][j - 1] + 1;
            else dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1]);
    }
}
vector<int> p[130];
vector<char> alp;
void solve() {
    for(int i = 0; i < 130; ++i) p[i].clear();
    for(int i = 0; i < lb; ++i) p[ b[i] ].push_back(i + 1);
    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 = '0'; i <= '9'; ++i) alp.push_back(i);
    int ans = 0;
    for(int i = 1; i <= la + 1; ++i) {
        for(int j = 0; j < alp.size(); ++j) {
            char c = alp[j];
            for(int k = 0; k < p[c].size(); ++k) {
                int r1 = i - 1;
                int r2 = la - i + 1;
                int r3 = p[c][k] - 1;
                int r4 = lb - p[c][k];
                if(dp1[r1][r3] + dp2[r2][r4] == K) { ans++; break; }
            }
        }
    }
    printf("%d
", 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 0;
}