/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static void lps
(String pattern ,
int lpsarr
[]) {
int len = 0;
int i = 0;
while(i < lpsarr.length)
{
if(pattern.charAt(i) == pattern.charAt(len))
{
lpsarr[i] = len;
len++;
i++;
}
else
{
while(pattern.charAt(i) == pattern.charAt(len))
{
if(len == 0)
{
lpsarr[i] = 0;
break;
}
len = lpsarr[len - 1];
}
}
}
}
{
// your code goes here
int lpsarr[] = new int[pattern.length()];
lps(pattern , lpsarr);
for(int i = 0 ; i < lpsarr.length ; i++)
{
System.
out.
print(lpsarr
[i
] + " "); }
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyB2b2lkIGxwcyhTdHJpbmcgcGF0dGVybiAsIGludCBscHNhcnJbXSkKCXsKCQlpbnQgbGVuID0gMDsKCQlpbnQgaSA9IDA7CgkJCgkJd2hpbGUoaSA8IGxwc2Fyci5sZW5ndGgpCgkJewoJCQlpZihwYXR0ZXJuLmNoYXJBdChpKSA9PSBwYXR0ZXJuLmNoYXJBdChsZW4pKQoJCQl7CgkJCQlscHNhcnJbaV0gPSBsZW47CgkJCQlsZW4rKzsKCQkJCWkrKzsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCXdoaWxlKHBhdHRlcm4uY2hhckF0KGkpID09IHBhdHRlcm4uY2hhckF0KGxlbikpCgkJCQl7CgkJCQkJaWYobGVuID09IDApCgkJCQkJewoJCQkJCQlscHNhcnJbaV0gPSAwOwoJCQkJCQlicmVhazsKCQkJCQl9CgkJCQkJbGVuID0gbHBzYXJyW2xlbiAtIDFdOwoJCQkJfQoJCQl9CgkJfQoJfQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CgkJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJCQoJCQoJCVN0cmluZyBwYXR0ZXJuID0gIkFBQUFBIjsKCQlpbnQgbHBzYXJyW10gPSBuZXcgaW50W3BhdHRlcm4ubGVuZ3RoKCldOwoJCWxwcyhwYXR0ZXJuICwgbHBzYXJyKTsKCQkKCQlmb3IoaW50IGkgPSAwIDsgaSA8IGxwc2Fyci5sZW5ndGggOyBpKyspCgkJewoJCQlTeXN0ZW0ub3V0LnByaW50KGxwc2FycltpXSArICIgIik7CgkJfQoJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJfQp9