算法(35)-异次元星人的文字

回文

 2024/03/15 

题目(hard)

外星文明中，异次元ABA星人的文字非常有特点，他们输出的文字翻译成地球上可见的字符串后，必定有英文字母，且正着看还是倒着看都是一样的，亦即：对于长度为n的字符串s，若i+j == n+1，那么s[i] = s[j], 其中i，j均为字符串位置下标，1<=i,j<=n，且n>=3

ABA星人于是将他们的间谍信息隐藏在地球字符中，便于传递消息，请你识别以下给出的几组字符串，并判断是否隐藏有ABA星文，有则输出能够匹配到的最长ABA星文的长度m，否则输出0。

给定长度为n的字符串L，1<=n<=10000, L由大小写字母和数字组成，其中ABA星文，其星文长度3<=m<=n。若找不到匹配的ABA星文，输出0

输入格式:
长度为n的字符串L，1<=n<=10000, L由大小写字母和数字组成，其中ABA星文，其星文长度m满足 3<=m<=n

输出格式:
输出能够匹配到的最长ABA星文的长度m，无则输出0

输入样例:
在这里给出一组输入。例如：

ABA3
AABBCC
00A00
输出样例:
在这里给出相应的输出。例如：

3
0
5

思路

var fs = require('fs');
var buf = '';

function isEN(c) {
  return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z';
}

function findLongestABA(L) {
  const n = L.length;
  let res = 0;
  for(let i = 0; i < 2 * n - 1; i++) {
    let left = Math.floor(i / 2);
    let right = left + i % 2;
    let temp = left === right ? -1 : 0;
    let hasEN = isEN(L[i]);
    while(left >= 0 && right < n && L[left] === L[right]) {
      hasEN = hasEN || isEN(L[left]);
      left--;
      right++;
      temp+=2;
    }
    res = temp > res && hasEN ? temp : res;
    if (res === n) {
      break;
    }
  }
  return res < 3 ? 0 : res;
}

process.stdin.on('readable', function() {
  var chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
  buf.split('\n').forEach(function(line) {
      if (line) {
        console.log(findLongestABA(line));
      }
  });
});

时间复杂度: O(n^2)。
空间复杂度: O(1)。

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/15/2024-03-15-%E7%AE%97%E6%B3%95(35)-%E5%BC%82%E6%AC%A1%E5%85%83%E6%98%9F%E4%BA%BA%E7%9A%84%E6%96%87%E5%AD%97/

发表日期：March 15th 2024, 11:48:55 pm

更新日期：March 17th 2024, 11:17:52 pm

Next Post

算法(36)-超级回文数
Previous Post

算法(34)-最长回文子串

CATALOG

1. 题目(hard)
2. 思路