密码截取

好吧，这两天面临着找实习工作的事了。然后huawei发过来一个账号，我打开就看到这道题了。

其实好久都没有编程了，脑子在这个当口转得还是比较慢的。

看了老半天，才发现，这个是输入一个随机字符串，求出它的最长对称字符串的长度。

所以，怎么做，就很明白了。

首先将原字符串进行倒置，然后进行移位比较，设置计数器，得到，相同的最大值。就像下面这样：

原串是str1=“avvbeeb”，将其翻转得到str2=“beebvva”，然后错位比较：

1： avvbeeb

str2：beebvva （上下对齐的元素是a;a比较）

2： avvbeeb

str2：beebvva （上下对齐的量元素av;va比较，不对称）

…………

11： avvbeeb

str2： beebvva （上下对齐的量元素beeb;beeb比较，得到最长对称子串）

…………

该方法要移动m+n次，每次元素比较个数从1到m不等，复杂度O（n2）;

就这样就求得了最长对称子串的长度了。

代码如下：

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int Maxsubstr(char a[],char b[])
 5 {
 6     int start1,start2;
 7     int count=0,Max=0;
 8     for(int i=0;a[i]!='\0';i++)
 9         for(int j=0;b[j]!='\0';j++)
10         {
11             start1=i;start2=j;
12             while(a[start1]==b[start2] && start1<strlen(a) && start2<strlen(b))
13             {
14                 start1++;
15                 start2++;
16                 count++;
17             }
18             if(count>Max)
19                 Max=count;
20             count=0;
21         }
22         return Max;
23 }
24 
25 char *Switch(char a[])
26 {
27     int n=strlen(a);
28     char temp;
29     for(int i=0;i<n/2;i++)
30     {
31         temp=a[i];
32         a[i]=a[n-1-i];
33         a[n-1-i]=temp;
34     }
35     return a;
36 }
37 
38 int main()
39 {
40     char a[80];
41     char b[80];
42     char *c;
43     gets(a);
44     strcpy(b,a);
45     c=Switch(a);
46     cout<<Maxsubstr(b,c);
47     return 0;
48 }

对称子串部分，引用了网友的一些总结，链接如下：http://www.jb51.net/article/48090.htm