Advanced Search

Ch1 : Calf Flac

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. /*
  2.   NAME : Nursoltan
  3.   PROB : calfflac
  4.   LANG : C++
  5.   DATE : 24/06/11 19:25
  6. */
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cctype>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <ctime>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <map>
  18. #include <set>
  19. #include <stack>
  20. #include <utility>
  21. #include <queue>
  22.  
  23. using namespace std;
  24.  
  25. #define MAX 100
  26. #define INF INT_MAX
  27. #define eps (1e-9)
  28.  
  29. #define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
  30. #define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
  31. #define CLR(_x) memset((_x),0,sizeof(_x))
  32. #define SQR(_x) ((_x)*(_x))
  33. #define all(_x) _x.begin(),_x.end()
  34. #define sz(_x) sizeof(_x)
  35.  
  36. #define vc vector<int>
  37. #define pb push_back
  38. #define mp make_pair
  39. #define iss istringstream
  40. #define oss ostringstream
  41. #define px first
  42. #define py second
  43.  
  44. typedef long long ll;
  45. typedef pair <int,int> point;
  46. int ABS(int _x){ return _x>0?_x:-_x; }
  47.  
  48. bool isLetter(char ch){
  49.      return ((ch>='A' && ch<='Z') || (ch>='a' && ch<='z'));
  50. }
  51.  
  52. char lower(char ch){
  53.      return (isupper(ch))?(ch-'A'+'a'):ch;
  54. }
  55.  
  56. char t[20005];
  57. int m;
  58.  
  59. int go(int i, int j){
  60.     int ret=0;
  61.     while(i>=0 && j<m && t[i]==t[j]) ret++,i--,j++;
  62.     return ret;
  63. }
  64.  
  65. int main(){
  66.     freopen("calfflac.in","r",stdin);
  67.     freopen("calfflac.out","w",stdout);
  68.  
  69.     int len,ret,b,e,n=0;
  70.     char s[20005];
  71.     int id[20005];
  72.  
  73.     CLR(s); CLR(id); CLR(t);
  74.     FOR(i,0,20005) id[i]=-1;
  75.  
  76.     char ch; 
  77.     while((ch=getchar())!=EOF) s[n++]=ch;
  78.  
  79.     m=0;
  80.     FOR(i,0,n) 
  81.       if(isLetter(s[i])){  
  82.         id[i]=m;
  83.         t[m++]=lower(s[i]);
  84.       }
  85.  
  86.     //FOR(i,0,m) cout<<t[i];
  87.     //cout<<endl;
  88.  
  89.     len=1; b=0; e=0;
  90.     FOR(i,0,m-1){
  91.       int k,_len;
  92.       k=go(i,i)-1;
  93.       _len=2*k+1;
  94.       if(_len>len){ len=_len; b=i-k; e=i+k+1; }
  95.  
  96.       k=go(i,i+1);
  97.       _len=2*k;
  98.       if(_len>len){ len=_len; b=i-k+1; e=i+k+1; }
  99.  
  100.       //cout<<go(i,i)<<" "<<go(i,i+1)<<endl;
  101.     }
  102.  
  103.     cout<<len<<endl;
  104.     int i=0;
  105.     while(id[i]==-1 || id[i]<b) i++;
  106.     while(i<n && id[i]==-1 || (id[i]>=b && id[i]<e)){
  107.       cout<<s[i];
  108.       if(id[i]==e-1) break;
  109.       i++;
  110.     }
  111.     cout<<endl;
  112.  
  113.     //system("pause");
  114.     return 0;
  115. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.