华为OJ字符串运用-密码截取

Myth丶恋晨 2022-06-17 01:23 195阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px"><p style="margin:21px 0cm 0px 24px; padding-top:0px; padding-bottom:0px; line-height:21px"><span style="font-size:14px">Catcher</span><span style="font-size:14px">是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化&nbsp;ABBA-&gt;12ABBA,ABA-&gt;ABAKK,123321-&gt;51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？</span></p><p style="margin-top:0px; margin-bottom:0px; margin-left:0in; padding-top:0px; padding-bottom:0px; vertical-align:baseline; unicode-bidi:embed; direction:ltr; text-indent:0in"><br style=""></p></pre> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 字符串,循环,函数,指针,枚举,位运算,结构体,联合体,文件操作,递归</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 输入一个字符串</p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 返回有效密码串的最大长度<br style=""> </p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> ABBA</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 4</td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>  
    #include <string>  
    #include <vector>
    #include <algorithm>
    //#include "Customer.h"
    
    #define Max(a,b) (a)>(b)?(a):(b)
    using namespace std;
    
    int getCatcher(string str, int i)
    {
    	int count1 = 0, count2 = 0;
    	int pre = i - 1;
    	int post = i + 1;
    
    	while (pre>=0 && post<str.length() && str[pre] == str[post] )
    	{
    		pre--;
    		post++;
    	}		
    	count1 = post - pre - 1;
    		
    	
    	pre = i;
    	post = i + 1;
    	while (pre >= 0 && post<str.length() && str[pre] == str[post] )
    	{
    		pre--;
    		post++;
    	}
    	count2 =  post - pre - 1;
    		
    	return Max(count1, count2);
    }
    int main()
    {
    	string str;
    	cin >> str;
    	int max = 0;
    	for (int i = 1; i < str.length(); i++)
    	{
    		max = Max(max, getCatcher(str, i));
    	}
    	cout << max;
    	return 0;
    }