Pagini recente » Cod sursa (job #2960482) | Cod sursa (job #1136490) | Cod sursa (job #1177919) | Cod sursa (job #282003) | Cod sursa (job #2803246)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2000005;
const int MAXP = 1000;
char a[MAXN], b[MAXN];
int urm[MAXN], pos[MAXP+1];
int main() {
fin >> (a + 1) >> (b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
int x = 0;
for(int i = 2; i <= n; i++) {
while(x && a[x + 1] != a[i])
x = urm[x];
if(a[x + 1] == a[i])
x++;
urm[i] = x;
}
int k = 0;
x = 0;
for(int i = 1; i <= m; i++) {
while(x && b[i] != a[x + 1])
x = urm[x];
if(b[i] == a[x + 1])
x++;
if(x == n) {
k++;
if(k <= MAXP)
pos[k] = i - n;
}
}
fout << k << "\n";
for(int i = 1; i <= min(k, MAXP); i++)
fout << pos[i] << " ";
fout << "\n";
return 0;
}