Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A palindrome is a string that reads the same from the left as it does from the right. Given two strings A and B, you need to find the length of longest palindrome which is a subsequence of both A and B. A subsequence is a sequence obtained by deleting zero or more characters from a string.

 

For example, say, A = “cfcfaafc”, B = “efagfc”. Then the longest palindrome which is a subsequence of both A and B is “faf”. So the answer is 3.

 

Input

First line of the input contains a positive integer T(T <= 100). Each of the following T cases consists of 2 lines. These 2 lines contain the strings A and B, respectively. Length of A and B will not be more than 60. All these strings contain only lowercase letters (‘a’ -‘z’). No empty strings will appear in the input.

 

Output

For each case, print a line of the form Case <x>: <y>, where x is the case number and y is the length of the longest common palindromic subsequence.

 

Sample Input

3

cfcfaafc

efagfc

afbcdfca

bcadfcgyfka

palin

drome

 

Sample Output

Case 1: 3

Case 2: 5

Case 3: 0

---

原本的方程推導 http://mypaper.pchome.com.tw/zerojudge/post/1324334213
從 220 ms 再加速 http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=477042

想法是這樣的，窮舉下一個匹配到的字符，然後進行 dp。
例如 [a ,,, a][a ,,, a] 是上次的, 窮舉 'a'-'z', 假使是 'e'
[a ... e ,,, e ... a][a ... e ,,, e ... a]
其中窮舉出來的字符間距離越大越好。


// 0.072 s
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxL (17000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
using namespace std;
int dp[65][65][65][65];
int appA[65][65], appB[65][65];
int mark[maxL];
char A[105], B[105];
int LA, LB;
int mapped[1008];
int dfs(int la, int ra, int lb, int rb) {
    if(la > ra || lb > rb)  return 0;
    if(GET((la<<18)|(ra<<12)|(lb<<6)|(rb)))
        return dp[la][ra][lb][rb];
    SET((la<<18)|(ra<<12)|(lb<<6)|(rb));
    int &ret = dp[la][ra][lb][rb];
    int sla, sra, slb, srb;
    int com = appA[la][ra]&appB[lb][rb], i;
    ret = 0;
    //for(int i = 'a'; i <= 'z'; i++) {
    while(com) {
        i = mapped[(com&(-com))%1007]+'a';
        com ^= com&(-com);
        sla = la;
        while(sla <= ra && A[sla] != i)     sla++;
        if(sla > ra)    continue;
        sra = ra;
        while(sra >= sla && A[sra] != i)    sra--;
        if(sra < sla)    continue;
        slb = lb;
        while(slb <= rb && B[slb] != i)     slb++;
        if(slb > rb)    continue;
        srb = rb;
        while(srb >= slb && B[srb] != i)    srb--;
        if(srb < slb)    continue;
        if(sla == sra || slb == srb)
            ret = max(ret, 1);
        else
            ret = max(ret, dfs(sla+1, sra-1, slb+1, srb-1)+2);
    }
    return ret;
}
int main() {
    for(int i = 0; i < 26; i++) {
        if(mapped[(1<<i)%1007])
            puts("error");
        mapped[(1<<i)%1007] = i;
    }
    int t, cases = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%s %s", &A, &B);
        LA = strlen(A), LB = strlen(B);
        memset(mark, 0, sizeof(mark));
        int usedA[128] = {}, usedB[128] = {};
        int i, j;
        for(i = 0; i < LA; i++)
            usedA[A[i]-'a'] = 1;
        for(i = 0; i < LB; i++)
            usedB[B[i]-'a'] = 1;
        for(i = 0, j = 0; i < LA; i++)
            if(usedB[A[i]-'a'])
                A[j++] = A[i];
        A[j] = '\0';
        for(i = 0, j = 0; i < LB; i++)
            if(usedA[B[i]-'a'])
                B[j++] = B[i];
        B[j] = '\0';
        LA = strlen(A);
        LB = strlen(B);
        if(LA == 0 || LB == 0) {
            printf("Case %d: 0\n", ++cases);
            continue;
        }
        for(i = 0; i < LA; i++) {
            appA[i][i] = 1<<(A[i]-'a');
            for(j = i+1; j < LA; j++) {
                appA[i][j] = appA[i][j-1]|(1<<(A[j]-'a'));
            }
        }
        for(i = 0; i < LB; i++) {
            appB[i][i] = 1<<(B[i]-'a');
            for(j = i+1; j < LB; j++) {
                appB[i][j] = appB[i][j-1]|(1<<(B[j]-'a'));
            }
        }
        printf("Case %d: %d\n", ++cases, dfs(0, LA-1, 0, LB-1));
    }
    return 0;
}
/*
100
gabgcccbadacg
gabxxxbacccgbadab
cfcfaafc
efagfc
afbcdfca
bcadfcgyfka
palin
drome
*/