Pagini recente » Cod sursa (job #569618) | Cod sursa (job #456321) | Cod sursa (job #2785357) | Cod sursa (job #823699) | Cod sursa (job #2066713)
#include <cstdio>
#include <cstring>
using namespace std;
char pat[2000005], txt[2000005];
int dp[2000005], n, m;
int nsol, sol[1005];
void buildPre() {
int len = 0, i = 1;
dp[0] = 0;
while(i < n) {
if(pat[len] == pat[i]) {
++ len;
dp[i] = len;
++ i;
} else {
if(len > 0) {
len = dp[len - 1];
} else {
dp[i] = 0;
++ i;
}
}
}
}
void searchKmp() {
int i = 0, j = 0;
while(j < m) {
if(pat[i] == txt[j]) {
++ i;
++ j;
}
if(i == n) {
++ nsol;
if(nsol <= 1000) {
sol[nsol] = j - i;
}
i = dp[i - 1];
} else if(j < m && pat[i] != txt[j]){
if(i > 0) {
i = dp[i - 1];
} else {
++ j;
}
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(pat);
gets(txt);
n = strlen(pat);
m = strlen(txt);
buildPre();
searchKmp();
printf("%d\n", nsol);
for(int i = 1; i <= nsol; ++ i) {
printf("%d ", sol[i]);
}
return 0;
}