华为OD机试 - 密码截获(Java/JS/Python/C/C++)

描述
Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些 “ABBA” 、“ABA”、“A”、“123321”。
但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化
“ABBA"→"12ABBA”、“ABA"→"ABAKK”，“123321"→"51233214”。因为截获的串太长了，而且存在多种可能的情况（ "abaaab"可看作是 "aba"或 “baaab”
的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

输入描述：
在一行上输入一个长度为1≦length(s)≦2500 ，仅由大小写字母和数字构成的字符串s，代表截获的密码。

输出描述：
在一行上输出一个整数，代表最长的有效密码串的长度。

示例

Java算法源码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.next();
		int count = 0; // 满足条件的子字符串的长度
		List<Integer> l = new ArrayList<Integer>(); // 存储遍历过程中的长度
		if (s.length() == 1) { // 边界值处理
			System.out.println(1);
		} else if (s.length() == 2) {
			if (s.charAt(0) == s.charAt(1)) {
				System.out.println(2);
			} else {
				System.out.println(1);
			}
		} else {
			for (int i = 0; i < s.length(); i++) { // 双指针遍历字符串
				for (int j = s.length() - 1; j >= i; j--) { // 参数j要满足条件j > i;一是防止substring()方法出错；
                                                            // 二是节省时间，因为i= 1，j = 5和i = 5，j = 1区间的子字符串是同一个
					
					if (s.charAt(i) == s.charAt(j) && isPalindromic(s.substring(i, j + 1))) {
						count = j - i + 1; // 存储本次遍历过程中满足条件的子字符串的长度
						l.add(count); // 将长度添加到集合l中
					}
				}
			}
			Collections.sort(l);
			System.out.println(l.get(l.size() - 1));
		}
	}

	// 判断字符串s是否为回文字符串
	public static boolean isPalindromic(String s) {
		if (s == null) {
			return false;
		}
		for (int i = 0, j = s.length() - 1; j > i; i++, j--) {
			if (s.charAt(i) != s.charAt(j)) {
				return false;
			}
		}
		return true;
	}
}

JavaScript算法源码：

Python算法源码：

C算法源码：

#include<stdio.h>
#include<string.h> // 使用函数时要用头文件：
#include<stdlib.h>
#include<ctype.h>
#include<stdbool.h> // 原来C语言里面是没有bool（布尔）类型的，可以支持CodeBlocks，C++里面才有。
#define LENGTH_MAX 2500 // s的长度为1≦length≦2500

int cmp_int(const void* p1, const void* p2) {
    return  *((int*)p1) - *((int*)p2);
}

char * substring(char * src, char * dest, int start, int length) {

    // 使用strncpy函数复制子字符串到目标字符串
    strncpy(dest, src + start, length - start);

    // 在目标字符串的末尾添加空字符
    dest[length - start] = '\0';

    return dest;
}


int main() {
    char s[LENGTH_MAX];
    char dest[LENGTH_MAX];
    bool isPalindromic(char * s);

    gets(s);

    int count = 0;
    int length[LENGTH_MAX] = {0}; // 存储遍历过程中的长度
    int length_num = 0;
    if(strlen(s) == 1) {
        printf("1\n");
    } else if(strlen(s) == 2) {
        if(s[0] == s[1]) {
            printf("2\n");
        } else {
            printf("1\n");
        }
    } else {
        for (int i = 0; i < ((int)(strlen(s))); i++) {
            for (int j = ((int)(strlen(s))) - 1; j >= i; j--) {
                if (s[i] == s[j] && isPalindromic(substring(s, dest, i, j + 1))) {
                    count = j - i + 1;
                    length[length_num] = count;
                    length_num++;
                }
            }
        }

        // 关键字qsort()函数对数组length进行排序，即由小到大排序(快速排序)
        qsort(length, sizeof length / sizeof length[0], sizeof(int), cmp_int); 
        
        printf("%d\n", length[sizeof length / sizeof length[0] - 1]);
    }
    return 0;
}

bool isPalindromic(char * s) {
    if (s == NULL) {
        return false;
    }
    for (int i = 0, j = strlen(s) - 1; j > i; i++, j--) {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}

C++算法源码：

#include <bits/stdc++.h>
#define LENGTH_MAX 2500
using namespace std;

char* substring(char src[], char dest[], int start, int length) {

    strncpy(dest, src + start, length - start);
    dest[length - start] = '\0';
    return dest;
}

int main() {
    char s[LENGTH_MAX];
    char dest[LENGTH_MAX];
    bool isPalindromic(char s[]);
    cin >> s;
    int count = 0;
    int length[LENGTH_MAX] = {0};
    int length_num = 0;
    if (strlen(s) == 1) {
        cout << "1" << endl;
    } else if (strlen(s) == 2) {
        if (s[0] == s[1]) {
            cout << "2" << endl;
        } else {
            cout << "1" << endl;
        }
    } else {
        for (int i = 0; i < ((int) (strlen(s))); i++) {
            for (int j = ((int) (strlen(s))) - 1; j >= i; j--) {
                if (s[i] == s[j] && isPalindromic(substring(s, dest, i, j + 1))) {
                    count = j - i + 1;
                    length[length_num] = count;
                    length_num++;
                }
            }
        }
        sort(length, length + length_num, [](const int& a, const int& b) {
            return a < b; // 对数组进行从小到大排序，x > y表示从大到小排序
            });
        cout << length[length_num - 1] << endl;
    }

    return 0;
}

bool isPalindromic(char s[]) {
    if (s == NULL) {
        return false;
    }
    for (int i = 0, j = strlen(s) - 1; j > i; i++, j--) {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}