Pagini recente » Cod sursa (job #622051) | Cod sursa (job #1227812) | Cod sursa (job #1066880) | Cod sursa (job #2781760) | Cod sursa (job #2030008)
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)2e6
char a[MAXN + 1];
char b[MAXN + 1];
#define in "strmatch.in"
#define out "strmatch.out"
int pi[MAXN + 1];
int an[MAXN + 1];
int main() {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
fgets(a + 1, MAXN + 1, stdin);
fgets(b + 1, MAXN + 1, stdin);
int n = strlen(a + 1) - 1, m = strlen(b + 1) - 1;
int k = 0;
for(int i = 2;i <= n;i++) {
while(k && a[i] != a[k + 1])
k = pi[k];
if(a[i] == a[k + 1])
k++;
pi[i] = k;
}
k = 0;
int ans = 0;
for(int i = 1;i <= m;i++) {
while(k && b[i] != a[k + 1])
k = pi[k];
if(b[i] == a[k + 1])
k++;
if(k == n) {
ans++;
an[ans] = i;
}
}
int aa = min(ans, 1000);
cout << ans << "\n";
for(int i = 1;i <= aa;i++)
cout << an[i] - n << " ";
return 0;
}