Pabon_SEC

Extend to Palindrome

Apr 11th, 2016
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define mx 100005
  3.  
  4. using namespace std;
  5.  
  6. char text[mx],pal[mx];
  7.  
  8. int suffix[mx],len;
  9.  
  10. void compute_suffix(const char *s)
  11. {
  12.     int i,j;
  13.  
  14.     for(i=1,j=0; s[i]; i++)
  15.     {
  16.         while(j && s[i]!=s[j])
  17.         {
  18.             j = suffix[j];
  19.         }
  20.  
  21.         if(s[i]==s[j])
  22.         {
  23.             j++;
  24.         }
  25.  
  26.         suffix[i+1] = j;
  27.     }
  28. }
  29.  
  30. int KMP_match(const char *s,const char *t)
  31. {
  32.     int i,j=0;
  33.  
  34.     for(i=0; i<len; i++)
  35.     {
  36.         while(j && s[j]!=t[i])
  37.         {
  38.             j = suffix[j];
  39.         }
  40.  
  41.         if(s[j]==t[i])
  42.         {
  43.             j++;
  44.         }
  45.     }
  46.  
  47.     return j;
  48. }
  49.  
  50. int main()
  51. {
  52.     int i,index;
  53.  
  54.     while(scanf("%s",text)!=EOF)
  55.     {
  56.         len = strlen(text);
  57.  
  58.         for(i=0; i<len; i++)
  59.         {
  60.             pal[i] = text[len-i-1];
  61.         }
  62.  
  63.         compute_suffix(pal);
  64.  
  65.  
  66.         index = KMP_match(pal,text);
  67.  
  68.         printf("%s",text);
  69.  
  70.         for(i=index;i<len;i++)
  71.         {
  72.             printf("%c",pal[i]);
  73.         }
  74.  
  75.         puts("");
  76.  
  77.     }
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment