|
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <cstdlib> #define INF 1000000 #define ll long long using namespace std; int main() { char s[100005]; string str; int len,i,j,idx; int *failureFunc; while(scanf("%s",s)!=EOF) { len=strlen(s); str=""; for(int y=len-1;y>=0;y--) str.append(1u,s[y]); failureFunc=(int *)malloc(sizeof(int)*len); failureFunc[0]=0; i=0; j=1; while(j<len) { if(str[i]==str[j]) { i+=1; failureFunc[j]=i; j+=1; } else { if(i) { i=failureFunc[i-1]; } else { failureFunc[j]=0; j+=1; } } } //match s and str(asume as pattern) i=0;j=0; int mx_idx=-1; while(i<len) { if(s[i]==str[j]) { i+=1;j+=1; mx_idx=j; } else { if(j) j=failureFunc[j-1]; else i+=1; } } string res=""; for(int y=j;y<str.size();y++) res.append(1u,str[y]); printf("%s",s); cout<<res<<"\n"; } return 0; } |