Find the Longest Repeated Prefix
National Olympiad — National round (2015 season)
Submission name: search.cpp
Problem summary
Choose the longest prefix that occurs again without overlapping that prefix. Report its length and the first possible 1-based starting column of its next occurrence.
Input
A decimal integer written as a digit string.
Output
The maximum prefix length and its next occurrence’s 1-based starting column. If no nonempty prefix repeats, print 0 1.
Constraints
1 ≤ string length < 10000000.
Worked example
An independently prepared example for this explanation.
Input
12312312312
Output
5 7
Solution analysis
- For every starting position i>0, compute Z[i], the number of matching characters between the prefix and the suffix beginning there. Use the standard Z window to reuse previous comparisons in linear time.
- A repeated prefix at i must have length at most Z[i], and nonoverlap additionally limits its length to i. Thus its best usable length is min(Z[i],i). Maximize this value, retaining the earliest starting position on ties.
- In 12312312312, the match at zero-based position 3 is long but can use only three digits without overlap. Position 6 matches five digits and supports length five, so the answer is length 5, column 7.
Why it works
Every valid second occurrence starts at some i and has length at most both Z[i] and i. Conversely the first min(Z[i],i) characters match and do not overlap. Maximizing over positions is therefore necessary and sufficient. Keeping the first maximizing position implements the editor’s first-next-occurrence rule.
Watch out. Overlapping matches are forbidden. Convert the selected zero-based position to a one-based column.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
// Algorithm: For every starting position i>0, compute Z[i], the number of matching characters
// between the prefix and the suffix beginning there.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string text;
cin>>text;
int n=static_cast<int>(text.size());
vector<int>z(n,0);
int left=0,right=0,best=0,column=1;
for(int i=1;i<n;++i){
if(i<right){
z[i]=min(right-i,z[i-left]);
}
while(i+z[i]<n&&text[z[i]]==text[i+z[i]]){
++z[i];
}
if(i+z[i]>right){
left=i;
right=i+z[i];
}
int usable=min(i,z[i]);
if(usable>best){
best=usable;
column=i+1;
}
}
cout<<best<<' '<<column<<'\n';
}