fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char next[100000];
  4. void compute_next(string &s)
  5. {
  6.   int slen = s.size();
  7.   next[0] = 0; /* initially next[q] = 0, first character in pattern */
  8.   int k = 0; /* no of char matched so far */
  9.   int q = 1;
  10.   while( q < slen )
  11.   {
  12.     while( k > 0 && s[k] != s[q] ) {
  13.       k = next[k-1];
  14.     }
  15.     if(s[k] == s[q])
  16.       k=k+1;
  17.     next[q] = k;
  18.     q++;
  19.   }
  20. }
  21.  
  22. int kmp_match(string &s, string &p)
  23. {
  24.   int slen = s.size();
  25.   /* calculate the next function on input string */
  26.   compute_next(p);
  27.   int q = 0; /* no of char matched so far */
  28.   int ind = 0, m = 0;
  29.   while(ind < slen) {
  30.     while(q > 0 && p[q] != s[ind])
  31.       q = next[q-1]; /* if char doesn't match, shift by taking value from next array */
  32.     if(p[q] == s[ind])
  33.       q = q+1; /* if matches, shift by 1, higher the q, longer the match */
  34.     m = max(m,q);
  35.     ind++;
  36.   }
  37.   /* return number of char matches so far */
  38.   return q;
  39. }
  40. bool is_palin(string &s)
  41. {
  42.    int len = s.size();
  43.    if( len < 2 ) return true;
  44.    for( int i = 0; i < (int)len/2; ++i)
  45.    {
  46.       if( s[i] != s[len-i-1])
  47.         return false;
  48.    }
  49.    return true;
  50. }
  51.  
  52. string reverse(const string &s)
  53. {
  54.   int sz = s.size();
  55.   string rev;
  56.   for(int i = 0; i < sz; ++i)
  57.     rev += s[sz-i-1];
  58.   rev.resize(sz);
  59.   return rev;
  60. }
  61.  
  62. int main()
  63. {
  64.   string line;
  65.   while(cin >> line)
  66.   {
  67.     if(is_palin(line))
  68.     {
  69.       cout << line << endl;
  70.     }
  71.     else
  72.     {
  73.       string rev = reverse(line);
  74.       int index = kmp_match(line, rev);
  75.       cout << line << rev.substr(index, rev.size()-1) << endl;
  76.     }
  77.   }
  78.   return 0;
  79. }
  80.  
Success #stdin #stdout 0s 3576KB
comments (?)
stdin
copy 
bcad
bcebccaedbabcbbd
ecacdcae
cde
dbbcedbe
cdeaa
bbabdcabbaaecb
bedcea
aec
edacdbddedbeeca
decbbeeaaedcbcccc
bbabbaeeeaebc
bbaeccbcdbabdeedbc
deaddaaebd
abbbaededbadaeeeecb
bcae
cbcdacebdaecadddd
debeddddbaed
deccbedad
ecaeaaeebec
ecc
edbcdedbdacbaabb
daabebcadbc
ecceabceeadbdbbadea
ebeb
dddaabbeaaebcbcabedc
dceebaccbbdcb
eebeebacadcaedae
ebb
ecccaaaceac
ddaeaebebcaeeeedbaa
c
edabcedbebeeccbebcdd
cdddbddddd
daecbdeabdcead
dcdcbacbadceba
baedcadbcecedec
dabcdebae
caceeeeaedacadbeecdc
deeacabebcbcacdb
ea
bcceab
cedad
babbebcdebaca
abdcccbeacac
aeeeabadcddbaebcbaec
ecdadd
dcedcdcebeaeddadedc
dd
eceedcedcbc
acb
abcebcbbbcaeadabbb
beb
dadba
cec
bebdce
eebcabadadeebaebaa
edddaccccadebdb
deedeccadeacec
acbdddd
badcbd
adaebbdaedebaadd
baeeac
dcbbaab
adbccbebaecceadc
adcaadeeccecaceeddb
d
ccdbddecceabcacbbedb
ddce
bcaededbb
acbeebabeeeadedbede
ccdcbcc
aa
aeabdcebbdadcbcabaec
bccebbacdaecc
bece
ccbbdacb
baaade
bacadeaabaddcdcba
daaacddcdacccbeb
eadeddadcabe
bccecbccbadde
babdeddddcaceaaa
dcccbdeeebeacebccb
caccecedabbeadbcc
edbacbabacabecbdbc
b
ceeceeaebcdebabeaee
ebbdee
cbdaeebdeadacddd
aaddbaddbb
caabbadaaeaeceeeeee
bbdeddebbabbcccecdb
ecd
dcccdccadcbdbdbea
adaaeedaceeabc
abdeadddcdb
aaadbdabceb
d
eedebeceadaddcee
stdout
copy 
bcadacb
bcebccaedbabcbbdbbcbabdeaccbecb
ecacdcaeacdcace
cdedc
dbbcedbebdecbbd
cdeaaedc
bbabdcabbaaecbceaabbacdbabb
bedceaecdeb
aecea
edacdbddedbeecaceebdeddbdcade
decbbeeaaedcbccccbcdeaaeebbced
bbabbaeeeaebcbeaeeeabbabb
bbaeccbcdbabdeedbcbdeedbabdcbcceabb
deaddaaebdbeaaddaed
abbbaededbadaeeeecbceeeeadabdedeabbba
bcaeacb
cbcdacebdaecaddddaceadbecadcbc
debeddddbaedeabddddebed
deccbedadebcced
ecaeaaeebecebeeaaeace
ecce
edbcdedbdacbaabbaabcadbdedcbde
daabebcadbcbdacbebaad
ecceabceeadbdbbadeaedabbdbdaeecbaecce
ebebe
dddaabbeaaebcbcabedcdebacbcbeaaebbaaddd
dceebaccbbdcbcdbbccabeecd
eebeebacadcaedaeadeacdacabeebee
ebbe
ecccaaaceacaecaaaccce
ddaeaebebcaeeeedbaabdeeeeacbebeaeadd
c
edabcedbebeeccbebcddcbebcceebebdecbade
cdddbdddddbdddc
daecbdeabdceadaecdbaedbcead
dcdcbacbadcebabecdabcabcdcd
baedcadbcecedececbdacdeab
dabcdebaeabedcbad
caceeeeaedacadbeecdceebdacadeaeeeecac
deeacabebcbcacdbdcacbcbebacaeed
eae
bcceabaeccb
cedadec
babbebcdebacabedcbebbab
abdcccbeacacaebcccdba
aeeeabadcddbaebcbaeceabcbeabddcdabaeeea
ecdaddadce
dcedcdcebeaeddadedcdedaddeaebecdcdecd
dd
eceedcedcbcdecdeece
acbca
abcebcbbbcaeadabbbadaeacbbbcbecba
beb
dadbabdad
cec
bebdcecdbeb
eebcabadadeebaebaabeabeedadabacbee
edddaccccadebdbedaccccaddde
deedeccadeacecaedaccedeed
acbddddbca
badcbdbcdab
adaebbdaedebaaddaabedeadbbeada
baeeacaeeab
dcbbaabbcd
adbccbebaecceadcdaecceabebccbda
adcaadeeccecaceeddbddeecacecceedaacda
d
ccdbddecceabcacbbedbdebbcacbaecceddbdcc
ddcecdd
bcaededbbdedeacb
acbeebabeeeadedbedebdedaeeebabeebca
ccdcbccbcdcc
aa
aeabdcebbdadcbcabaeceabacbcdadbbecdbaea
bccebbacdaecceadcabbeccb
beceb
ccbbdacbcadbbcc
baaadedaaab
bacadeaabaddcdcbabcdcddabaaedacab
daaacddcdacccbebcccadcddcaaad
eadeddadcabebacdaddedae
bccecbccbaddeddabccbceccb
babdeddddcaceaaaecacddddedbab
dcccbdeeebeacebccbecaebeeedbcccd
caccecedabbeadbccbdaebbadececcac
edbacbabacabecbdbcebacababcabde
b
ceeceeaebcdebabeaeeaebabedcbeaeeceec
ebbdeedbbe
cbdaeebdeadacdddcadaedbeeadbc
aaddbaddbbddabddaa
caabbadaaeaeceeeeeeceaeaadabbaac
bbdeddebbabbcccecdbdcecccbbabbeddedbb
ecdce
dcccdccadcbdbdbeaebdbdbcdaccdcccd
adaaeedaceeabcbaeecadeeaada
abdeadddcdbdcdddaedba
aaadbdabcebecbadbdaaa
d
eedebeceadaddceecddadaecebedee
https://ideone.com/ulpHXV
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!