#include<iostream>
#include<cstdio>
#include<cstring>
#define mx 1000010
using namespace std;
char text[mx],pattern[mx];
int failur[mx],cnt,len;
void failur_()
{
int i=1,j=0;
while(i<len)
{
if(pattern[i]==pattern[j])
{
j++;
failur[i]=j;
i++;
}
else if(j>0)
{
j=failur[j-1];
}
else
{
failur[i]=0;
i++;
}
}
}
void KMP()
{
failur_();
int i=0,j=0;
while(i<len)
{
if(text[i]==pattern[j])
{
j++;
i++;
cnt=j;
}
else if(j>0)
{
j=failur[j-1];
}
else
{
i++;
}
}
}
int main()
{
while(scanf("%s",text)==1)
{
len=strlen(text);
for(int i=len-1,j=0; i>=0; i--,j++) pattern[j]=text[i];
cnt=0;
KMP();
// cout<<cnt<<endl;
cout<<text;
for(int i=cnt; i<len; i++) cout<<pattern[i];
cout<<endl;
}
return 0;
}
#include<cstdio>
#include<cstring>
#define mx 1000010
using namespace std;
char text[mx],pattern[mx];
int failur[mx],cnt,len;
void failur_()
{
int i=1,j=0;
while(i<len)
{
if(pattern[i]==pattern[j])
{
j++;
failur[i]=j;
i++;
}
else if(j>0)
{
j=failur[j-1];
}
else
{
failur[i]=0;
i++;
}
}
}
void KMP()
{
failur_();
int i=0,j=0;
while(i<len)
{
if(text[i]==pattern[j])
{
j++;
i++;
cnt=j;
}
else if(j>0)
{
j=failur[j-1];
}
else
{
i++;
}
}
}
int main()
{
while(scanf("%s",text)==1)
{
len=strlen(text);
for(int i=len-1,j=0; i>=0; i--,j++) pattern[j]=text[i];
cnt=0;
KMP();
// cout<<cnt<<endl;
cout<<text;
for(int i=cnt; i<len; i++) cout<<pattern[i];
cout<<endl;
}
return 0;
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন