Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply print the maximum length in a line.
Sample Input:
|
1 |
Is PAT&TAP symmetric? |
Sample Output:
|
1 |
11 |
Update: 2016/3/23 增加了使用了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<stdio.h> #include<stdlib.h> int main() { char buf[2002],c; int rl[2002],max_right=0,pos=0,max=0,n,i=0; while((c=getchar())!='\n') { buf[i++]=1; buf[i++]=c; } buf[i++]=1; buf[i]=0; rl[0]=1; n=i; for(i=1;i<n-max;i++) { if(i>max_right) { rl[i]=1; } else { rl[i]=rl[2*pos-i]>max_right-i?max_right-i:rl[2*pos-i]; } while(i-rl[i]>=0&&i+rl[i]<n&&buf[i+rl[i]]==buf[i-rl[i]]) { rl[i]++; } if(i+rl[i]-1>max_right) { pos=i; max_right=i+rl[i]-1; } if(rl[i]>max) { max=rl[i]; } } printf("%d\n",max-1); } |
的版本
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<stdio.h> #include<string.h> int main() { char buf[1001]; int i,j,k,n,count=0,another_count=0,max=1; gets(buf); n=strlen(buf); for(i=0;i<n-1;i++) { count=1; another_count=1; if(buf[i]==buf[i+1]) { count=2; for(j=i-1,k=i+2;j>=0&&k<n;j--,k++) { if(buf[j]==buf[k]) { count+=2; } else { break; } } } if(i+2<n&&buf[i]==buf[i+2]) { another_count=3; for(j=i-1,k=i+3;j>=0&&k<n;j--,k++) { if(buf[j]==buf[k]) { another_count+=2; } else { break; } } } count=count>another_count?count:another_count; if(max<count) { max=count; } } printf("%d\n",max); } |