UVa11151 - Longest Palindrome (LCS)

題目大意：

給你一個字串，詢問在這字串中能夠找到的最長迴文長度為多少。
迴文：從左邊讀與右邊讀相同

分析：

這題可以使用兩種方式解，但我這裡只用其中一種方式解題，原因是解決速度較快，但缺點時間複雜度較高。

QUESTION 1: 哪兩種方式呢

• 最長共同子序列 Longest Common Subsequence (LCS)
  時間複雜度為 \(O(n^2)\)
• 馬拉車演算法 Manacher’s Algorithm
  時間複雜度為 \(O(n)\)

這裡我們使用時間複雜度比較高的演算法，最長共同子序列

QUESTION 2: 那為甚麼我們會使用最長共同子序列，時間複雜度比較高呀！

因為這題的字串長度不超過 1000，且題目有說明 \(90 \% \) 的測試資料長度都小於 255。通常時間複雜度 \(O(n^2)\) 只要測試資料大小不大於 \(10^3\) 基本上都可以通過。加上如果只有 LCS 去寫這題目可以讓這題目簡單非常多。

也可以透過題目給的測試資料範圍大小來猜這題的時間複雜度

QUESTION 3: 通常 LCS 應該要有兩個字串來找出共同子序列但這題是迴文，哪裡有關係呢？

嘿嘿，這個我其實一開始也想不到但後來我在 google 翻找文章時看到了一個超級優秀的想法！顛覆了我的想像。

必須要有兩個子串，第一個為題目給的字串，第二為題目反轉字串，並將他們進行 LCS 就可以把找到他們的共同子序列，那也就是迴文啦!

Why?

由於迴文的特性，你如果顛倒反著念也會一樣，剛好符合共同子序列，因為迴文就算顛倒還是一樣呀www。

EXERCISE A:

求 ADAM 與 MADA 的 LCS

答案是不是會是 3 呢！很神奇吧，國人的演算法思維真的大於大於我，我好爛嗚嗚ಥ⌣ಥ。

參考連結

uva 11151 Longest Palindrome （最长公共子序列）
APCS - 2018台南一中選修

心得

其實我還沒有學好 Manacher’s Algorithm，有點怠惰阿我！還需要更努力，明明有一個中秋廉價我的努力卻沒有變多有點討厭啊！我需要讓我自己變得能夠專心，有時候我在打 blog 文章時，我都會有種腦袋已經想好要打甚麼，但手指卻沒有跟上QAQ，難道是老了嗎…，不會吧！

不過打心得的時候是快樂的，因為可以把自己想講的話抒發出來，認識的人不太會看到不會尷尬，也不會被他們覺得虛偽XD，我好希望我能夠把生活中的每件事情都記錄在 blog 上，但感覺還是有點難，有時候遇到一些討厭的事情通常都是會選擇跟朋友分享，有點少打在 Blog 上，我也希望我可以打打我的愛情故事在 Blog 上，但我又很怕之後被朋友們 judge。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1010
using namespace std;
int dp[MAXN][MAXN] = {} ;
string strA , strB ;
int n , m ;

int lcs(){
    n = strA.length();
    m = strB.length();
    for(int i = 0 ; i <= n ; i++) dp[i][0] = 0 ;
    for(int j = 0 ; j <= m ; j++) dp[j][0] = 0 ;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            if(strA[i-1] == strB[j-1]) dp[i][j] = dp[i-1][j-1]+1 ;
            else dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
        }
    }
    return dp[n][m] ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int t ;
    cin >> t ;
    cin.ignore();
    while(t--){
        getline(cin,strA);
        strB = strA ;
        reverse(strB.begin() , strB.end());
        cout << lcs() << '\n' ;
    }

    return 0;
}