首页 > 试题广场 >

密码截取

[编程题]密码截取
  • 热度指数：277402 时间限制：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找出最长的有效密码串吗？

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm length}(s) \leqq 2500 ，仅由大小写字母和数字构成的字符串 s ，代表截获的密码。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表最长的有效密码串的长度。
示例1

输入

ABBA

输出

4

说明

\hspace{15pt}在这个样例中，没有无关字符，所以最长的有效密码串就是 \texttt{ 本身，长度为 4 。
示例2

输入

12HHHHA

输出

4

说明

\hspace{15pt}在这个样例中，最长的有效密码串是 \texttt{ ，长度为 4 。
算法知识视频讲解
添加回答
C
牛客429262880号头像 牛客429262880号 
#include <stdio.h>

int check_password(char* pas){
    int len = strlen(pas);

    for (int i = len - 1; i >= 0; i --){
        if (pas[i] == pas[0]){
            for (int n = 0, m = i; m >= n; n += 1, m -= 1){
                if (pas[n] != pas[m]){
                    break;
                } else{
                    if (m == n || m - 1 < n + 1){
                        return i + 1;
                    }
                }
            }
        }
    }

    return 0;
}

int main() {
    char password[2501];
    scanf("%s", password);

    int len = 0;

    for (int i = 0; i < strlen(password) - len; i ++){
        len = len > check_password(password + i) ? len : check_password(password + i);
        
    }

    if (strlen(password) == 1)
        printf("1");
    else
        printf("%d", len);
    
    return 0;
}

发表于 2025-02-07 16:37:34 回复(0)
C
江理吴彦祖头像 江理吴彦祖
// 获取到字符串后，两次嵌套for循环，i从0到长度减一，j从i+1到长度，如果两个下标对应的字符相同，获取一下j和i的差值，如果是1，那么他们就是紧紧相连的，所以长度就是2，记录一下。如果是2，那么就是中间隔了一个，所以长度就是3,。这两种情况一定是对称的，所以不用什么计算，直接得到就好了
// 剩下的就是长一点的对称字符串。一种是偶数个数，先判断 j - i 的差值对2取余是否不为零，此时分出来长度是偶数的情况，另一种就是奇数了
// 接着，在偶数时，得到他们中间有几个对称的数字，将它除以2，也就是我们要比几次，for循环这个次数，每成功一次，就将变量b加一，紧接着长度变量a就等于2乘以比的次数加上头和尾的两个数，所以就是a = b * 2 + 2.   一旦失败，就break跳出这次for循环，直接进入下一次查找，因为他已经不属于对称了。记得将两个变量变回去0.  如果全都成功了，那么就先比较之前记录的长度是否被现在记录的长度超过了，也就是更新长度
// 如果是奇数，同理，只不过就在循环比较中间的字符时，在最后一次比较时，直接将长度加一就好了，


#include <stdio.h>
#include <string.h>

int main() {
    char str[2500];
    gets(str);
    int length = strlen(str);
    int sonCharLength = 1;
    int a = 0;
    int b = 0;
    for(int i = 0; i < length-1; i++)
    {
        for(int j = i + 1; j < length; j++)
        {
            if(str[i] == str[j])
            {
                if((j - i) == 1)
                {
                    a = 2;
                   
                }
                else if((j - i) == 2)
                {
                    a = 3;
                }
                else if((j - i) % 2 != 0) // 偶数个
                {
                    for(int m = 1; m <= (j - i)/2; m++)
                    {
                        if(str[i+m] == str[j-m])
                        {
                            b++;
                            a = b * 2 + 2;
                        }
                        else {
                            a = 0;
                            break;
                        }
                    }
                    b = 0;
                }
                else if((j - i) % 2 == 0)   // 奇数个
                {
                    for(int m = 1; m <= (j-i) / 2; m++)
                    {
                        if(m != (j-i) / 2)
                        {
                            if(str[i+m] == str[j-m])
                            {
                                b++;
                                a = b * 2 + 2;
                            }
                            else {
                                a = 0;
                                break;
                            }
                        }
                        else if(m == (j-i) / 2)
                        {
                            a += 1;
                        }
                    }
                }
                if(sonCharLength < a)
            {
                sonCharLength = a;
                b = 0;
                a = 0;
            }
            }
            b = 0;
            a = 0;
        }
    }
    printf("%d", sonCharLength);
    return 0;
}
发表于 2024-07-21 18:36:41 回复(0)
C
千墨头像 千墨 
#include <stdio.h>
#include <string.h>

int main() {
    int i, j;
    int left, right;
    int res, Max = 0;
    char str[2501];
    while (scanf("%s", str) != EOF) { // 注意 while 处理多个 case
        int len = strlen(str);
        for (i = 1; i < len; i++) {
            res = 0;
            left = right = i;            //奇数对称
            res = 1;

            while (left >= 1 && right <= len - 2) {
                if (str[--left] == str[++right])
                    res += 2;
                else break;
            }

            Max = res > Max ? res : Max;
        }
        for (i = 1; i < len-1; i++) {
            res = 0;    //注意每个循环开始清零
            if (str[i] == str[i + 1]) { //偶数对称
                left = i;
                right = i + 1;
                res = 2;
            
                while (left >= 1 && right <= len - 2) {
                    if (str[--left] == str[++right])
                        res += 2;
                    else break;
                }
            }	//记住偶数循环必须在整个if条件里面
            Max = res > Max ? res : Max;

        }
        printf("%d", Max);
        return 0;
    }
}

发表于 2024-06-24 11:25:21 回复(0)
C
牛客356249919号头像 牛客356249919号 
//对称的密码长度有奇偶两种
//先找最中间对称的那两个或者三个字符
//以此为起点向两边搜索，并更新最大的对称长度

#include <stdio.h>
#include <string.h>

int main() {
    char str[2501] = {'\0'};
    gets(str);
    int ec = 0;
    int s = 0 , e = 0;
    //两个窗口滑动
    for(int i = 0; i < strlen(str) - 2; i++){
        if(str[i] == str[i + 1]){
            s = i - 1;
            e = i + 2;
            while(s >= 0 && e <= strlen(str) - 1 && str[s] == str[e]){
                --s,++e;
            }
            if(ec < e - s - 1) ec = e - s - 1;
        }
    }    

    //三个窗口滑动
    for(int i = 0; i < strlen(str) - 3; i++){
        if(str[i] == str[i + 2]){
            s = i - 1;
            e = i + 3;
            while(s >= 0 && e <= strlen(str) - 1 && str[s] == str[e]){
                --s,++e;
            }
            if(ec < e - s - 1) ec = e - s - 1;
        }
    } 

    printf("%d",ec);
    return 0;
}

编辑于 2023-12-23 21:27:08 回复(0)
C
彭洋a头像 彭洋a
#include <stdio.h>
#include <string.h>

//判断是不是对称密码
int ispassword(char* left, char* right)
{
    while (left <= right)
    {
        if (*left - *right == 0)
        {
            left++;
            right--;
        }
        else {
            return 0;
        }
    }
    return 1;
}

int main() {
    char str[2501] = { '\0' };
    //记录有效密码的最大长度
    int ret = 0;
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        for (int i = 0; i < len - 1; i++)
        {
            for (int j = i + 1; j < len; j++)
            {
                if (str[i]-str[j] == 0)
                {
                    int flag = ispassword(&str[i], &str[j]);
                    if (flag == 1 && j - i +1> ret)
                    {
                        ret = j - i + 1;
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
   
    return 0;
}
发表于 2023-10-10 17:23:54 回复(0)
C
牛客364244344号头像 牛客364244344号 
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define N 2501

void FindMaxOushu(char s[], int index, int* cnt, int len)
{
    int left = index - 1;
    int right = index + 2;
    int temp = 2;
    while(1){
        if(left < 0 || right >= len){
            break;
        }
        if(s[left] == s[right]){
            left--, right++;
            temp += 2;
        }else{
            break;
        }
    }
    *cnt = temp > *cnt ? temp : *cnt;
}

void FindMaxJishu(char s[], int index, int* cnt, int len)
{
    int left = index - 1;
    int right = index + 3;
    int temp = 3;
    while(1){
        if(left < 0 || right >= len){
            break;
        }
        if(s[left] == s[right]){
            left--, right++;
            temp += 2;
        }else{
            break;
        }  
    }
    *cnt = temp > *cnt ? temp : *cnt;
}

int main()
{
    char s[N] = {0};
    scanf("%s", s);
    int len = strlen(s);
    int cnt = 0;
    for(int i = 0; i < len-1; i++){
        // 1.遍历查找偶数长的
        if(s[i] == s[i+1]){
            FindMaxOushu(s, i, &cnt, strlen(s));
        }
    }
    for(int i = 0; i < len-2; i++){
        // 2.遍历查找奇数长的
        if(s[i] == s[i+2]){
            FindMaxJishu(s, i, &cnt, strlen(s));
        }
    }
    printf("%d\n", cnt);
    return 0;
}

发表于 2023-10-05 17:48:43 回复(0)
C
Jackn头像 Jackn 
#include <stdio.h>
#include <string.h>

int main() {
    char code[2501];
    scanf("%s",code);
    int max=1,len=0,len1,tempi;
    for(int i=0; i<strlen(code); i++){
        len=i,tempi=1;
        len1=i+1;
        if(i>=strlen(code)-i-1) len1=len=strlen(code)-i-1;
        for(int j=1; j<=len&&code[i-j]==code[i+j]; j++,tempi+=2);
        if(tempi>max) max=tempi;
        tempi=0;
        for(int j=1; j<=len1&&code[i-j+1]==code[i+j]; j++,tempi+=2);
        if(tempi>max) max=tempi;
    }
    printf("%d\n",max);
    return 0;
}

发表于 2023-06-05 16:49:06 回复(0)
C
Riko1头像 Riko1
c递归：只有两种可能，一种自己为中心，一种两边：
#include <stdio.h>
#include <string.h>
int max=0,temp=0;
char str[2500];
int length;
int find(int front,int last){
    if(front>=0&&last<length&&str[front]==str[last]){
        if(front==last){
        temp=temp+1;
        }
        else{
            temp=temp+2;
        }
        max=(max>temp)?max:temp;
       return find(front-1,last+1);
    }
    else{
        max=(max>temp)?max:temp;
        temp=0;
        return max;
    }
}
int main() {
    while (scanf("%s", str) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        length=strlen(str);
        for(int i=1;i<length;i++){
         
            max=(find(i-1,i)>find(i,i))?find(i-1,i):find(i,i);
       
        }
        printf("%d\n",max);
    }
    return 0;
}

发表于 2023-04-05 10:55:02 回复(1)
C
牛客623637102号头像 牛客623637102号
//20行代码以内
#include <stdio.h>
int main()
{
    char st[2500];
    int i,j,k,len,flg1,lmax=-10000;
    scanf("%s",st);
    len=strlen(st);
    for(i=0;i<len;i++)
    {
        for(j=len-i;j>1;j--)
        {   
            flg1=1;
            for(k=0;k<j/2;k++) if(st[i+k]!=st[i+j-k-1]) {flg1=0;break;} 
            if(j>=lmax && flg1>0) lmax=j; 
        }
    }
   printf("%d",lmax); 
}
发表于 2022-06-01 22:07:07 回复(0)
C
已注销头像 已注销 
#include <stdio.h>
#include <string.h>
#define    N    2500
int main()
{
    char str[N];
    gets(str);
    int len=strlen(str),i=0,j,k,left,right,flag;
    while(len-i>0)
    {
        flag=0;
        for(j=0;j<=i;j++)
        {
            left=j;right=len-i+j-1;
            while(left<right)
            {
                if(str[left]!=str[right])
                    break;
                left++;right--;
            }
            if(left>=right)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
            break;
        i++;
    }
    printf("%d\n",len-i);
    return 0;
}

发表于 2022-04-27 09:40:05 回复(0)
C
奋斗boy.头像 奋斗boy.
#include <stdio.h>
#include <string.h>

int main()
{
    int i, j, k;
    int len;
    int cnt;
    int max = 0;
    char arr[3000];

    while (scanf("%s", arr) != EOF)
    {
        len = strlen(arr);

        for (i = 0; i < len; i++)
        {
            for (j = len - 1; j > i; j--)
            {
                cnt = 0;
                for (k = 0; k < (j - i + 1) / 2; k++)
                {
                    if (arr[i+k] == arr[j-k])
                    {
                        cnt++;
                    }
                    else
                    {
                        cnt = 0;
                        break;
                    }
                }

                cnt *= 2;
                if (cnt > 0)
                {
                    if ((j-i+1) % 2 > 0)
                    {
                        cnt += 1;
                    }
                }

                if (cnt > max)
                {
                    max = cnt;
                }
            }
        }

        printf("%d\r\n", max);
    }
}

发表于 2022-03-31 22:20:07 回复(0)
C
WoundedWolf头像 WoundedWolf
C语言求解法——暴力位移循环遍历
思路：1、输入数组字符串，从最开始的下标进行遍历，遍历的长度逐渐增加，终止条件为出现非回文（即两边不对称），做差输出最大回文长度
2、对最开始的下标进行向后位移，并调用回文最大判别函数（即第一步中步骤），对输出的最大回文值进行比较大小，留下较大值，则最终的值即为最大回文值。
C语言代码如下：
//HJ32 密码截取
#include<stdio.h>
#include<string.h>
int PassWord(char *num,int a,int b)
{
    int count=0;
    for(int i=0;i<=(b-a)/2;i++)
    {
        if(num[a+i]!=num[b-i])
            return 0;
    }
    return (b-a+1);
}
int main()
{
    char str[20000];
    while(scanf("%s",&str)!=EOF)
    {
        int count=0;
        for(int i=0;i<strlen(str);i++)
        {
            for(int j=i+count-1;j<strlen(str);j++)
            {
                if(count<PassWord(str,i,j))
                    count=PassWord(str,i,j);
            }
        }
        printf("%d\n",count);
    }
}


发表于 2021-07-30 16:22:30 回复(2)
C
校长_头像 校长_ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char str[10000] = {0};
    int len;
    while(scanf("%s", str) != EOF){
        int MaxNum = 0;
        int Num = 0;
        len = strlen(str);
        if(len-1 == 0)   {
            Num++;
            printf("%d\n", Num);
        }
        else{
            for(int i = 0; i < len; i++){
                int left = i;
                for(int right = len-1; right >= i; right--){
                    if(str[left] == str[right] && left != right) {
                        Num += 2;
                        left++;
                        if(left == right) {
                            MaxNum = MaxNum > Num ? MaxNum : Num;
                            left = i;
                            Num = 0;
                        }
                            
                    }
                    else if(left == right && str[left-1] == str[right+1]){
                        Num++;
                        MaxNum = MaxNum > Num ? MaxNum : Num;
                        left = i;
                        Num = 0;
                    }
                    else  {
                        if(Num != 0)
                            right++;
                        Num = 0;
                        left = i;
                        
                    }
                }
                
            }
            printf("%d\n", MaxNum);
            
        }
    }
}

发表于 2021-07-21 00:12:41 回复(0)
提交观点

问题信息

动态规划 字符串
难度：
14条回答 45724浏览

热门推荐

通过挑战的用户

查看代码

相关试题

密码截取

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号