题解 | #密码截取#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 解题思路：通过动态规划
// 定义状态:dp[i][j]=true，表示从i到j为回文字符串
// 初始化状态
// 状态转移方程：input[i]=input[j]，则dp[i][j]取决于dp[i+1][j-1]，如果不相等，则dp[i][j]=false
// 打印结果maxSubLen
void (async function () {
    // Write your code here
    while ((input = await readline())) {
        const inputLen = input.length;
        let maxSubLen = 1;
        let dp = Array.from({ length: inputLen }, (value,index) =>
            Array(index+1).fill(false)
        );
        for (let i = 0; i < inputLen; i++) {
            dp[i][i] = true;
        }
        for (let curLen = 2; curLen <= inputLen; curLen++) {
            if(curLen<maxSubLen)break;
            for (let i = 0; i <= inputLen - curLen; i++) {
                let j = i + curLen - 1;
                if (input[i] == input[j] && (curLen==2||dp[i + 1][j - 1])) {
                    maxSubLen = curLen;
                    dp[i][j] = true;
                }
            }
        }
        console.log(maxSubLen);
    }
})();