Pagini recente » Cod sursa (job #1130349) | Cod sursa (job #2012888) | Cod sursa (job #2064006) | Cod sursa (job #2204747) | Cod sursa (job #855887)
Cod sursa(job #855887)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAXN 2100000
int N, M, prefix[MAXN], v[MAXN];
char A[MAXN], B[MAXN];
void doPrefix() {
prefix[1] = 0;
for (int i = 2, p = 0; i <= M; ++i) {
while (p > 0 && A[i] != A[p + 1])
p = prefix[p];
if (A[i] == A[p + 1])
++p;
prefix[i] = p;
}
}
int main() {
fin.getline(A + 1, MAXN);
fin.getline(B + 1, MAXN);
M = strlen(A + 1);
N = strlen(B + 1);
doPrefix();
for (int i = 1, j = 0; i <= N; ++i) {
while (j > 0 && B[i] != A[j + 1])
j = prefix[j];
if (B[i] == A[j + 1])
++j;
if (j == M && v[0] < 1000)
v[++v[0]] = i - M;
}
fout << v[0] << "\n";
for (int i = 1; i <= v[0]; ++i)
fout << v[i] << " ";
return 0;
}