126B – Password

This problem is based on Z- algorithm

To learn this algorithm  – Click here!

 

View Code

#include<bits/stdc++.h>
using namespace std;
void solve(string s)
{
int l=s.size();
int z[l];
int left,right;
left=right=0;
for(int k=1;k<l;k++) { if(k>right)
{
left=right=k;
while(right {
right++;
}
z[k]=right-left;
right–;
}
else{
int k1=k-left;
if(z[k1]<right-k+1)
{
z[k]=z[k1];
}
else{
left=k;
while(right {
right++;
}
z[k]=right-left;
right–; }

}
}
int mxz = 0, res = 0,n=l;
for(int a=1;a<l;a++){
//printf(“%d %d\n”, a, Z[a]);
if(a + z[a] == l){
if(z[a] <= mxz){
for(int j=0;j<z[a];j++) printf(“%c”, s[j]); return ; } } mxz = max(mxz, z[a]); } puts(“Just a legend”); } int main() { string s; cin>>s;

solve(s);
}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s