Print how many times a pattern appears in a text, counting overlapping matches, and where. Use KMP, so the text is read only once.
What to build
A KMP search that reports every match of a pattern, including overlapping ones.
Requirements
- Build the lps table for the pattern first.
- Never move back in the text.
- After a full match, carry on from
lps[m - 1].
Input
Two lines: the text, then the pattern. Each is a word of 1 to 1000 letters with no spaces. Upper and lower case are different letters.
Output
The first line has the number of matches. The second line has their starting positions (counting from 0) separated by spaces, or none if there are no matches.
Constraints
The text and pattern each have 1 to 1000 letters, with no spaces.
Example
Input:
ABABDABACDABABCABAB
ABABCABAB
Output:
1
10
Why it works
The lps table records how much of the pattern is still matched after a mismatch or a full match, so the text index only moves forward and no match is missed.
Examples
ABABDABACDABABCABAB ABABCABAB
1 10
aaaa aa
3 0 1 2
Hints
Hint 1
First build lps for the pattern: lps[i] is the length of the longest proper prefix of pattern[0..i] that is also its suffix.
Hint 2
Search with i over the text and j over the pattern. On a mismatch with j > 0, set j = lps[j - 1] and compare again; never move i back.
Hint 3
When j reaches m, record i - m + 1, then set j = lps[m - 1] so overlapping matches are found.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
char text[1001], pat[1001];
int lps[1001], found[1001];
int main(void) {
scanf("%1000s %1000s", text, pat);
int n = strlen(text), m = strlen(pat);
for (int i = 1, len = 0; i < m;) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
int count = 0;
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && text[i] != pat[j]) j = lps[j - 1];
if (text[i] == pat[j]) j++;
if (j == m) {
found[count++] = i - m + 1;
j = lps[m - 1];
}
}
printf("%d\n", count);
if (count == 0) printf("none\n");
for (int k = 0; k < count; k++) printf(k ? " %d" : "%d", found[k]);
if (count) printf("\n");
return 0;
}