首页 > 试题广场 >

密码截取

[编程题]密码截取
  • 热度指数:253841 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214 。因为截获的串太长了,而且存在多种可能的情况(abaaab可看作是aba,或baaab的加密形式),Cathcer的工作量实在是太大了,他只能向电脑高手求助,你能帮Catcher找出最长的有效密码串吗?

数据范围:字符串长度满足

输入描述:

输入一个字符串(字符串的长度不超过2500)



输出描述:

返回有效密码串的最大长度

示例1

输入

ABBA

输出

4
示例2

输入

ABBBA

输出

5
示例3

输入

12HHHHA

输出

4
// 获取到字符串后,两次嵌套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)
#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)
//对称的密码长度有奇偶两种
//先找最中间对称的那两个或者三个字符
//以此为起点向两边搜索,并更新最大的对称长度

#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)
#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)
#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)
#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递归:只有两种可能,一种自己为中心,一种两边:
#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)
//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)
#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)
#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语言求解法——暴力位移循环遍历
思路: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)
#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)