Pagini recente » Cod sursa (job #2447595) | Cod sursa (job #2488345) | Cod sursa (job #2986925) | Cod sursa (job #2319780) | Cod sursa (job #1871427)
#include <stdio.h>
#include <vector>
#include <cstring>
#define nmax 2000010
using namespace std;
int n, m, k, nr;
int pred[nmax];
char s[nmax], ss[nmax];
vector <int> ans;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(s + 1); n = strlen(s + 1);
gets(ss + 1); m = strlen(ss + 1);
pred[1] = 0; k = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && s[i] != s[k + 1]) k = pred[k];
if (s[i] == s[k + 1]) k++;
pred[i] = k;
}
k = 0;
for (int i = 1; i <= m; i++) {
while (k > 0 && ss[i] != s[k + 1]) k = pred[k];
if (ss[i] == s[k + 1]) k++;
if (k == n) {
nr++;
if (ans.size() < 1000) ans.push_back(i - n);
k = pred[k];
}
}
printf("%d\n", nr);
for (int i = 0; i < (int)ans.size(); i++) printf("%d ", ans[i]);
return 0;
}