首页 > 试题广场 >

密码截取

[编程题]密码截取

热度指数：262950 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

在一行上输入一个长度为  ，仅由大小写字母和数字构成的字符串  ，代表截获的密码。

输出描述:

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

示例1

输入

ABBA

输出

说明

在这个样例中，没有无关字符，所以最长的有效密码串就是  本身，长度为  。

示例2

输入

12HHHHA

输出

说明

在这个样例中，最长的有效密码串是  ，长度为  。

算法知识视频讲解

Java

新的旅程a

来一个动态规划版的，时间和空间复杂度都是O(n)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.next();
        int max = 0;
        int[] dp = new int[input.length()]; //当前回文字符串长度
        dp[0] = 1;
        for(int i=1;i<input.length();i++){
            if(i-1-dp[i-1]>=0 &&input.charAt(i)==input.charAt(i-1-dp[i-1])){//在上一个回文字符串的基础上，分别往左右扩大1位
                dp[i] = dp[i-1] + 2; //如：AB->ABA,ABB->ABBA,ABCB->ABCBA
            } else if(input.charAt(i)==input.charAt(i-1)){//当前字符和上一个字符相等时
                //分为是否连续相等。如：ABC->ABCC,ABB->ABBB
                dp[i] = i>=2&&input.charAt(i-1)==input.charAt(i-2)?dp[i-1]+1:2;
            } else if(i>3&&input.charAt(i)==input.charAt(i-2)){//当前字符和i-2个字符相等
                //是否为ABABA->ABABAB这种循环形式的。循环形式的和前一个dp相等，否则为3
                dp[i] = input.charAt(i-1)==input.charAt(i-3)?dp[i-1]:3;
            } else{
                dp[i] = 1;
            }
            max = Math.max(dp[i],max);
        }
        System.out.println(max);
    }
}

发表于 2024-11-04 05:10:28 回复(0)

Java

Ding_Lifeng

Java 动态规划

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            // 动规--确定回文串的最大长度
            String code = in.nextLine();
            int len = code.length();
            if(len == 1)
                System.out.println(1);

            // dp[i][j] - 目标字符串i到j是否为回文串， i>j为false i=j为true
            // 状态转移方程
            // dp[i][j] = dp[i+1][j-1] || charAt(i) == charAt(j) (j-i>1)
            // dp[i][j] = charAt(i) == charAt(j) (j-i=1)
            // 答案-dp[i][j] = true , max(j-i+1)
            boolean[][] dp = new boolean[len][len];
            int maxLen = 1;
            for(int i=0; i<len; i++)  // j=i边界条件
                dp[i][i] = true;

            for(int l=2; l<=len; l++){  // 循环条件为子串长度，子串长度由短至长
                for(int i=0; (i+l-1)<len; i++){
                    int j = i+l-1;
                    if(code.charAt(i)==code.charAt(j)){
                        if(l==2)
                            dp[i][j] = true;
                        else
                            dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] == true)
                        maxLen = Math.max(maxLen,l);
                }
            }
            System.out.println(maxLen);
        }
    }
}

发表于 2024-08-30 14:29:01 回复(0)

Java

牛客317900105号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int len = 0;
            for (int i = 0; i < str.length(); i++) {
                for (int j = str.length() - 1; j > i; j--) {
                    len = Math.max(findStr(str, i, j),len);
                }
            }
            System.out.println(len);
        }
    }

    //此方法用来寻找从小索引到大索引的子串的长度
    public static int findStr(String str, int i, int j) {
        int a = i;
        int b = j;
        boolean is = true;
        while (i < j){
            if (str.charAt(i) == str.charAt(j)){
                i++;
                j--;
            }else {
                is = false;
                break;
            }
        }
        if (is)
            return b - a + 1;
        else
            return 0;
    }
}

发表于 2024-07-05 16:33:53 回复(0)

Java

热血的三文鱼躺平了

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String s = in.nextLine();

        char[] c = s.toCharArray();

        System.out.print(checkStr(c));

    }

    public static int checkStr(char[] c){
        int m = 0;
        for(int i = 0; i<c.length; i++)
        {
            for(int j = c.length-1; j>i; j--)
            {
                int n = cS(c,i,j);
                m = m<n?n:m;
            }
        }
        return m;
    }

    public static int cS(char[] c, int i, int j)
    {
        if(i<=j){
            if(c[i]==c[j])
                if(i!=j)
                    return 2+cS(c,i+1,j-1);
                else
                    return 1;
            else
                return -2500;
        }
        return 0;
    }
}

发表于 2024-05-04 21:52:35 回复(0)

Java

老师我太想进步溜

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int res = 0;
        for (int i = 0; i < str.length(); i++) {
            int len1 = calLen(str, i, i);
            int len2 = calLen(str, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }

        System.out.println(res);
    }

    private static int calLen(String str, int l, int r) {
        while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

编辑于 2024-03-09 16:21:04 回复(0)

Java

SnailTree

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String inputStr = in.nextLine();
        int max = inputStr.length();
        boolean flag = true;
        while (flag) {
            if (checkStr(inputStr)) {
                flag = false;
                break;
            }
            for (int i = 0; i + max < inputStr.length(); i++) {
                if (checkStr(inputStr.substring(i, i + max))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                max--;
            }

        }
        System.out.println(max);

    }
    private static boolean checkStr(String str) {
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != str.charAt(str.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

发表于 2024-01-03 16:38:52 回复(0)

Java

今生能进大厂吗

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            int count = 0;
            int max = 0;
            for (int i = 1; i < s.length() - 1; i++) {
                char c = s.charAt(i);
                //ABA
                while (true) {
                    //对于字符c 它的前一个字符等于后一个字符属于ABA型
                    //i-1-count >=0 && i+1+count< s.length()左右边界控制
                    if (i - 1 - count >= 0 && i + 1 + count < s.length() &&
                            s.charAt(i - 1 - count) == s.charAt(i + 1 + count)) {
                        count++;
                    } else {
                        if (count > 0) {
                            max = max > count * 2 + 1 ? max : count * 2 + 1;
                            count = 0;
                        }
                        break;
                    }
                }
                //ABBA  对于字符c 它等于后一个字符属于ABBA型
                if (c == s.charAt(i + 1)) {
                    while (true) {
                        //i-1-count >=0 && i+2+count< s.length()左右边界控制
                        if (i - 1 - count >= 0 && i + 2 + count < s.length() &&
                                s.charAt(i - 1 - count) == s.charAt(i + 2 + count)) {
                            count++;
                        } else {
                            if (count > 0) {
                                max = max > count * 2 + 2 ? max : count * 2 + 2;
                                count = 0;
                            }
                            break;
                        }
                    }
                }
            }
            System.out.println(max);

        }
    }
}

编辑于 2023-12-29 10:30:00 回复(0)

Java

虎图图

思路

1.设置一个方法判断字符串是否为满足题目要求的回文字符串

2.遍历输入的字符串，利用双指针、substring()方法截取不同的子字符串代入方法看是否满足条件

3.设置一个集合，存储遍历过程中的长度，输出最长长度

要点

使用双指针遍历时，外层遍历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区间的字符串是同一个

public class HJ032 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int count = 0;      //满足条件的子字符串的长度
        List<Integer> l = new ArrayList<>();   //存储遍历过程中的长度
        if(s.length() == 1){        //边界值处理
            System.out.println(1);
            return;
        }
        if(s.length() == 2){
            if(s.charAt(0) == s.charAt(1)){
                System.out.println(2);
                return;
            }else{
                System.out.println(1);
                return;
            }
        }
        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是否为回文字符串
     * @param s
     * @return
     */
    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;
    }

}

发表于 2023-09-21 00:27:33 回复(0)

Java

陈六狗

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int arr[] = new int[str.length() * 2 - 3];
        int index = 0;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j <= i && i + j + 1 < str.length(); j++) {
                if (i - j == 0 || i + j + 1 == str.length() - 1) {
                    if (str.charAt(i - j) == str.charAt(i + j + 1)) {
                        arr[index] = (j + 1) * 2;
                        index++;
                        break;
                    } else {
                        arr[index] = j * 2;
                        index++;
                        break;
                    }
                } else {
                    if (str.charAt(i - j) == str.charAt(i + j + 1)) {

                    } else {
                        arr[index] = j * 2;
                        index++;
                        break;
                    }
                }
            }
        }
        for (int i = 1; i < str.length(); i++) {
            for (int j = 0; i - j - 1 >= 0 && i + j + 1 < str.length(); j++) {
                if (i - j - 1 == 0 || i + j + 1 == str.length() - 1) {
                    if (str.charAt(i - j - 1) == str.charAt(i + j + 1)) {
                        arr[index] = (j + 1) * 2 + 1;
                        index++;
                        break;
                    } else {
                        arr[index] = j * 2 + 1;
                        index++;
                        break;
                    }
                } else {
                    if (str.charAt(i - j - 1) == str.charAt(i + j + 1)) {

                    } else {
                        arr[index] = j * 2 + 1;
                        index++;
                        break;
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.println(max);
    }
}

发表于 2023-09-18 16:05:00 回复(0)

Java

牛客546909688号

求大神问为什么案例结果是7啊，我怎么看都觉得案例不对啊

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        //将字符串反转
        StringBuffer reverseStr = new StringBuffer("");
        for(int i=str.length()-1;i>=0;i--){
            reverseStr.append(str.charAt(i));
        }

        //比较两个字符串的相同的字符串
        int count = 0;
        int startIndex = 0;
        int endIndex = 0;
        boolean isNewStart = false;
        for(int i=0;i<str.length();i++){
            //如果显示相等，分两种情况，1）开关若是关闭，说明是第一个相等的，开始计算开始位置，开关打开  2）开关打开，说明计数已经开始，endIndex设为当前index
            if(str.charAt(i) == reverseStr.charAt(i)){
                if(isNewStart){//开关打开
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                }else{
                    startIndex = i;
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                    isNewStart = true;
                }
            }else{
                //如果显示不等，也分两种情况，1）开关关闭，未开始计数，跳转下一个字符  2）开关打开，计数开始，endIndex设为当前index，计算长度count,若大于原count，赋值给原count,开关关闭
                if(isNewStart){//开关打开
                    endIndex = i+1;
                    int newCount = endIndex - startIndex;
                    if(newCount > count){
                        count = newCount;
                    }
                    isNewStart = false;
                }else{
                    continue;
                }
            }
        }
        System.out.println(count);
    }
}

案例：

tmikrmvnkzwffmuycgffiqnrepltnfvnggtmwkzmpjpcfuhmdcdlrupmqbimvppbnqinwcuidfckveonfgcknihwztkvrikfunegxfboluzjhxkoxdvdxoczqdkyjziqmjnnrbvcolyxijemlujjofuojdwfhcgzmmnsznhbv

发表于 2023-09-09 23:36:50 回复(0)

Java

爱交友的柠檬精在抱佛脚

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
      public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String str = in.nextLine();
        int max = 1;

        for (int i = 0; i < str.length() / 2; i++) {
            for (int j = i+1; j <=str.length(); j++) {

                String s1 = str.substring(i, j);
                if (find(s1)) {
                    if (max < s1.length()) {
                        max = s1.length();
                    }
                }
            }

        }
        System.out.println(max);

    }

    public static boolean find(String str) {
        if(str.length()%2==0){
                 StringBuffer sb = new StringBuffer();
        String str1 = str.substring(0, str.length() / 2);
        String str2 = sb.append(str.substring(str.length() / 2 )).reverse().toString();
        if (str1.equals(str2)) {
            return true;
        }

        }else{
            StringBuffer sb = new StringBuffer();
            String str1 = str.substring(0,str.length()/2);
            String str2 = sb.append(str.substring(str.length() / 2 +1)).reverse().toString();
           if (str1.equals(str2)) {
            return true;
        }
        }

       
        return false;
    }
}

发表于 2023-08-15 22:03:57 回复(0)

Java

牛客781396821号

思路一：暴力解法：对于每个字符，从后向前寻找它的回文字符串，记录最长的

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            int num = 0, length = a.length();
            // 确定字符
            for (int i = 0 ; i < length ; i++) {
                char c = a.charAt(i);
                // 开始遍历
                for (int j = length - 1 ; j >= i ; j--) {
                    char ch = a.charAt(j);
                    // 相同：寻找回文字符串；不同：继续寻找
                    if (c == ch) {
                        int i1 = i + 1, j1 = j - 1;
                        for (; i1 <= j1 ; i1++, j1--) {
                            if (a.charAt(i1) != a.charAt(j1)) {
                                break;
                            }
                        }
                        if (i1 >= j1) {
                            num = num > j - i ? num : j - i + 1;
                        }
                    }
                }
            }
            System.out.println(num);
        }
    }
}

思路二：从中心寻找：对于每个字符，向两侧寻找它的回文字符串，记录最长的；如果它和它后面的字符相同，则从中心两个字符开始寻找

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            int num = 0, length = a.length();
            // 确定字符
            for (int i = 0 ; i < length ; i++) {
                char c = a.charAt(i);
                // 从中心单个字符为基准开始寻找回文字符串长度
                int j = i - 1;
                int k = i + 1;
                for (; j >= 0 && k < length ; j--, k++) {
                    if (a.charAt(j) != a.charAt(k)) {
                        break;
                    }
                }
                // 计算时，这两个字符不同，需要回退一步
                j++;
                k--;
                num = num > (k - j + 1) ? num : k - j + 1;
                // 如果它和它后面的字符相同，从中心两个字符为基准开始寻找回文字符串长度
                if ((i < length - 1) && (c == a.charAt(i + 1))) {
                    for (j = i - 1 , k = i + 2; j >=0 && k < length ; j--, k++) {
                        if (a.charAt(j) != a.charAt(k)) {
                            break;
                        }
                    }
                    j++;
                    k--;
                    num = num > (k - j + 1) ? num : k - j + 1;
                }
            }
            System.out.println(num);
        }
    }
}

发表于 2023-05-25 11:43:38 回复(0)

Java

joyvvvv

public class Test01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            //dp[i][j]表示下标i-j是否是回文，不是值为0，是值为子串长度
            //这里可以使用Boolean[][]dp，如果是回文更新max长度。
            int[][] dp = new int[str.length()][str.length()];
            //i==j，表示只有一位，初始化时都是回文，长度为1；
            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = 1;
            }
            int max = 0;
            //i从下往上遍历，j从左至右遍历
            for (int i = dp.length - 1; i >= 0 ; i--) {
                //j>i,所以从i+1开始遍历
                for (int j = i + 1; j < dp[0].length ; j++) {
                    if (str.charAt(i) == str.charAt(j)) {
                        //特殊情况两位相等 值为2
                        if (j - i == 1) {
                            dp[i][j] = 2;
                        } else {
                            //如果[i+1][j-1]是回文，[i][j]+2
                            dp[i][j] =dp[i+1][j-1]==0?0:dp[i+1][j-1]+2;
                        }
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            System.out.println(max);
        }
    }
}

发表于 2023-05-16 20:59:36 回复(0)

Java

牛客604637229号

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNext()) { // 注意 while 处理多个 case

String a = in.next();

TreeMap<Integer,String> treeMap = new TreeMap<Integer,String>();

for(int i=0;i<a.length();i++){

for(int j=a.length();j>i;j--){

StringBuffer bf = new StringBuffer();

String substr = a.substring(i,j);

boolean flag = true;

int substrlen = substr.length();

//根据dp[i]=dp[len-1-i]表达式进行规划

for(int k=0;k<(int)(substrlen/2);k++){

if(substr.charAt(k)!=substr.charAt(substrlen-1-k)){

flag = false;

break;//当前的中断，只是本循环的中断

}

if(flag){

treeMap.put(substrlen,substr);

}

System.out.println(treeMap.lastEntry().getKey());

}

发表于 2023-04-20 00:44:19 回复(0)

Java

focuser

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 使用双指针法,从中心点到两边扩散,注意有两种星形式的回文子串
        String str = in.nextLine();
        // 定义左右指针
        int l;
        int r;
        // 定义集合接收回文字符的长度
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length() - 2; i++) {
            // ABBA型
            int len1 = 0;
            if (str.charAt(i) == str.charAt(i + 1)) {
                // 两边发散继续寻找
                l = i;
                r = i + 1;
                do {
                    len1 += 2;
                    l--;
                    r++;
                } while (r < str.length() && str.charAt(l) == str.charAt(r));
            }
            // ABA型 不是加2 初始值是1
            int len2 = 1;
            if (str.charAt(i) == str.charAt(i + 2)) {
                // 两边发散继续寻找
                l = i;
                r = i + 2;
                do {
                    len2 += 2;
                    l--;
                    r++;
                    //防止数组越界异常前置判断
                } while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r));
            }
            list.add(Math.max(len1, len2));
        }
        System.out.println(Collections.max(list));

    }
}

双指针法,人人都能看懂

发表于 2023-04-14 23:33:09 回复(2)

提交观点

问题信息

动态规划字符串

难度：

72条回答 2982收藏 43040浏览

通过挑战的用户

查看代码

奈何笑不了

2023-03-02 15:21:52
牛客80860...

2023-02-20 12:14:13
牛客15248...

2023-01-25 01:58:19
帅阿衰

2023-01-07 17:18:12
dailypa...

2022-11-01 10:07:26

密码截取

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

思路

要点

问题信息

热门推荐

通过挑战的用户

相关试题