The KMP table holds more information than it seems. Use it to find the pattern inside a word.
What to build
A program that prints the lps table of a word and uses it to find the word's shortest repeating unit.
Requirements
- Build the lps table in O(n).
- Find the shortest block that makes up the whole word when repeated a whole number of times.
- Print the table, and then the length of the block and the number of repeats.
Input
One word with no spaces.
Output
Two lines: the lps table, values separated by spaces, and then the block length and the number of repeats.
Constraints
The word has 1 to 500 letters.
Example
Input:
abab
Output:
0 0 1 2
2 2
Why it works
If the longest prefix that is also a suffix has length L, the word overlaps itself when shifted by n − L. That shift is the word's shortest period, and it is a repeating unit only when it divides n exactly.
Examples
abab
0 0 1 2 2 2
AABA
0 1 0 1 4 1
Hints
Hint 1
Build the lps table exactly as KMP does.
Hint 2
Let `p = n - lps[n - 1]`. If `n` is divisible by `p`, the word is a block of length `p` repeated.
Hint 3
Otherwise the only unit is the whole word.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
int lps[500];
int main(void) {
char w[501];
scanf("%500s", w);
int n = strlen(w), len = 0;
lps[0] = 0;
for (int i = 1; i < n;) {
if (w[i] == w[len]) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
for (int i = 0; i < n; i++) printf("%d ", lps[i]);
printf("\n");
int p = n - lps[n - 1];
if (n % p != 0) p = n;
printf("%d %d\n", p, n / p);
return 0;
}