Pagini recente » Cod sursa (job #2770676) | Cod sursa (job #238994) | Cod sursa (job #2347529) | Cod sursa (job #3235684) | Cod sursa (job #2211443)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int LMAX = 2000001;
char a[LMAX], b[LMAX];
int n, m, u[LMAX], pot[LMAX], nrp;
void urm() {
int k = -1, x;
u[0] = 0;
for(x = 1; x < n; x++) {
while(k > 0 && a[k+1] != a[x]) k = u[k];
if(a[k+1] == a[x]) k++;
u[x] = k;
}
}
int main()
{
in >> a >> b;
n = strlen(a);
m = strlen(b);
int x = -1;
urm();
for(int i = 0; i < m; i++) {
while(x > 0 && a[x+1] != b[i]) x = u[x];
if(a[x+1] == b[i]) x++;
if(x == n-1) {
pot[++nrp] = i-n+1;
x = u[x];
}
}
out << nrp << '\n';
for(int i = 1; i <= nrp && i <= 1000; i++)
out << pot[i] << ' ';
return 0;
}