Pagini recente » Cod sursa (job #122005) | Cod sursa (job #1769528) | Cod sursa (job #333987) | Cod sursa (job #1654871) | Cod sursa (job #1774114)
#include <fstream>
#include <cstring>
#define min(a,b) (a<b?a:b)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=2000010;
int lena, lenb, i, j, p[N], rez[N], nr, x;
char a[N], b[N];
int main() {
fin >> a + 1;
fin >> b + 1;
lena = strlen(a + 1);
lenb = strlen(b + 1);
p[1] = 0;
for (i = 2; i <= lena; ++i) {
x = p[i - 1];
while (a[i] != a[x + 1] && x != 0)
x = p[x];
if (a[i] == a[x + 1]) {
p[i] = x + 1;
} else {
p[i] = 0;
}
}
x = 0;
for (i = 1; i <= lenb; ++i) {
while (b[i] != a[x + 1] && x!=0)
x = p[x];
if (b[i] == a[x + 1]) {
x++;
}
if (x == lena) {
rez[++nr] = i - lena;
x = p[x];
}
}
fout << nr << "\n";
for (i = 1; i <= min(nr, 1000); ++i) {
fout << rez[i] << ' ';
}
fout << "\n";
return 0;
}