A border (verge,
brink) of a string is any proper prefix of this string that is equal
to its suffix.
For example, the
string S = abaababaabaab has two non-empty borders: ab and abaab.
The string S = abaabaab also has two such borders – ab and abaab, with the second border being overlapping.
A string of
length n consisting of a repeated character (for example, aaaaaaaa or a8) has n – 1 borders. For S = a8 these borders are: a, aa, aaa,
aaaa, aaaaa, aaaaaa, aaaaaaa.
The term “proper prefix” excludes the
border that coincides with the entire string.
The length
of a border is the number of characters it contains.
A natural
generalization of the notion of a border is the longest border – the longest
proper prefix of the string that is equal to its suffix.
Input. One string S (|S|
≤ 106).
Output. Print the length of the longest
border of the string S.
|
Sample
input |
Sample
output |
|
abaabaab |
5 |
strings – prefix function
Construct the prefix
function for the string S and store it in the array p. If the length of S is n,
then to solve the problem it is enough to print the value p[n – 1].
Build the prefix function
of the input string s in the array p.
string s;
vector<int> p;
The function MaxBorderArray
computes the prefix function for the string s.
vector<int> MaxBorderArray(string &s)
{
vector<int> p(s.size());
// p[0] = 0
for (int i = 1;
i < s.size(); i++)
{
int j = p[i - 1];
while ((j > 0)
&& (s[i] != s[j]))
j = p[j - 1];
if (s[i] == s[j]) p[i] = j + 1; else p[i] = 0;
}
return p;
}
Build the prefix function
for the string s using the MaxBorderArray function.
cin >> s;
p =
MaxBorderArray(s);
Print the length of the
longest border of the string, which is stored in p[s.size() – 1].
printf("%d\n", p[s.size() - 1]);