Pagini recente » Cod sursa (job #1725482) | Cod sursa (job #2251792) | Cod sursa (job #286003) | Cod sursa (job #2625235) | Cod sursa (job #855888)
Cod sursa(job #855888)
#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[++v[0]] = i - M;
}
fout << v[0] << "\n";
for (int i = 1; i <= v[0] && i <= 1000; ++i)
fout << v[i] << " ";
return 0;
}