Pagini recente » Cod sursa (job #976726) | Cod sursa (job #2036676) | Cod sursa (job #3143469) | Cod sursa (job #1761593) | Cod sursa (job #1774112)
#include <fstream>
#include <cstring>
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 <= nr; ++i) {
fout << rez[i] << ' ';
}
fout << "\n";
return 0;
}