Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Codeforces #246 Div 2 D: Prefixes and Suffixes
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 100005;
char S[MAX];
int Z[MAX];
int C[MAX];
int main(int argc, char **argv)
{
scanf("%s", S);
int n = strlen(S);
Z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (r < i) {
l = r = i;
while (S[r] == S[r-l])
r++;
Z[i] = r - l;
} else {
int b = r - i;
int j = i - l;
if (Z[j] < b) {
Z[i] = Z[j];
} else if (Z[j] > b) {
Z[i] = b;
} else {
l = i;
r = i + b;
while (S[r] == S[r-l])
r++;
Z[i] = r - l;
}
}
}
for (int i = 0; i < n; i++)
C[i] = Z[i];
sort(C, C + n);
int length = 1;
vector< pair<int, int> > ans;
for (int i = n - 1; i >= 0; i--) {
if (Z[i] == length) {
int t = (C + n) - lower_bound(C, C + n, length);
ans.push_back(make_pair(length, t));
}
length++;
}
printf("%d\n", ans.size());
for (pair<int, int> p : ans)
printf("%d %d\n", p.first, p.second);
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.