Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define mx 100005
- using namespace std;
- char text[mx],pal[mx];
- int suffix[mx],len;
- void compute_suffix(const char *s)
- {
- int i,j;
- for(i=1,j=0; s[i]; i++)
- {
- while(j && s[i]!=s[j])
- {
- j = suffix[j];
- }
- if(s[i]==s[j])
- {
- j++;
- }
- suffix[i+1] = j;
- }
- }
- int KMP_match(const char *s,const char *t)
- {
- int i,j=0;
- for(i=0; i<len; i++)
- {
- while(j && s[j]!=t[i])
- {
- j = suffix[j];
- }
- if(s[j]==t[i])
- {
- j++;
- }
- }
- return j;
- }
- int main()
- {
- int i,index;
- while(scanf("%s",text)!=EOF)
- {
- len = strlen(text);
- for(i=0; i<len; i++)
- {
- pal[i] = text[len-i-1];
- }
- compute_suffix(pal);
- index = KMP_match(pal,text);
- printf("%s",text);
- for(i=index;i<len;i++)
- {
- printf("%c",pal[i]);
- }
- puts("");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment