PATA1040题解（疑问）

#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<map>#include<set>#include<cstring>#include<stdio.h>using namespace std;char ch[5000];int len;/*  把第三个的判断方法和第二个的暴力方法结合在了一起，通过了*/int test(int i, int flag) {    int temp = -1, j, ans=-1e9;    if(flag == 1) {        temp = 1;        j = 1;        while((i-j>=0) && (i j<len) && (ch[i-j] == ch[i j])) {            j  ;            temp  = 2;        }        return temp;    }else {        if(ch[i-1] == ch[i]) {            temp = 0;            j = 1;            while((i-j>=0) && (i j-1<len) && (ch[i-j] == ch[i j-1])) {            j  ;            temp  = 2;            }            ans = temp;        }else if(ch[i 1] == ch[i]) {            temp = 0;            j = 1;            while((i-j 1>=0) && (i j<len) && (ch[i-j 1] == ch[i j])) {            j  ;            temp  = 2;            }            ans = max(temp,ans);        }        return ans;    }}int main() {    //FILE *fp = fopen("1.txt","r");    fgets(ch, 2000, stdin);    len = strlen(ch)-1;    int cur = 0, ans = 1;    for(int i = 0; i < len; i  ) {        cur = max(test(i,0),test(i,1));        ans = max(cur, ans);    }    cout << ans;}/* 第二个想的暴力解决方法，但是有两个测试点过不去，不知道什么地方错了。。int main() {    //FILE *fp = fopen("1.txt","r");    fgets(ch, 2000, stdin);    len = strlen(ch)-1;    int cur = 0, ans = 1;    for(int i = 0; i < len-1; i  ) {        for(int j = i 1; j < len; j  ) {            cur = 0;            for(int k = i, l = 0; k <= j; k  , l  ) {                    int rt = j-l, lt = i l;                    if(rt == lt) {                        cur  = 1;                        break;                    }                    if(rt < lt || ch[rt] != ch[lt]) break;                    cur  = 2;            }            ans = max(ans,cur);        }    }    cout << ans;}*//*最初想到的办法，分治，我觉得算法复杂度应该是nlgn，但实际运行起来很慢int test(int i, int flag) {    int temp = -1, j, ans=-1e9;    if(flag == 1) {        temp = 1;        j = 1;        while((i-j>=0) && (i j<len) && (ch[i-j] == ch[i j])) {            j  ;            temp  = 2;        }        return temp;    }else {        if(ch[i-1] == ch[i]) {            temp = 0;            j = 1;            while((i-j>=0) && (i j-1<len) && (ch[i-j] == ch[i j-1])) {            j  ;            temp  = 2;            }            ans = temp;        }else if(ch[i 1] == ch[i]) {            temp = 0;            j = 1;            while((i-j 1>=0) && (i j<len) && (ch[i-j 1] == ch[i j])) {            j  ;            temp  = 2;            }            ans = max(temp,ans);        }        return ans;    }}int traverse(int i, int j) {  if(i < 0 || j < 0) return 0;    if(i > j) return 0;    if(i == j) return 1;    int mid = (i j)/2;    int ans = max(traverse(i,mid), traverse(i 1,j));    int p = max(test(mid,0),test(mid,1));    return max(ans,p);}int main() {    FILE *fp = fopen("1.txt","r");   fgets(ch, 2000, fp);   len = strlen(ch) ;   cout << traverse(0, len-1);}*/