11475

#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;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *