Pagini recente » Cod sursa (job #2794976) | Cod sursa (job #366856) | Cod sursa (job #488314) | Cod sursa (job #144472) | Cod sursa (job #1420740)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
int min(int a, int b) {
return a < b ? a : b;
}
using namespace std;
int main() {
string A, B;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> A >> B;
int M = A.length();
int N = B.length();
A = " " + A;
B = " " + B;
vector<int> pi(M + 1, 0);
vector<int> pos(1010, 0);
int q = 0;
for (int i = 2; i <= M; ++i) {
while (q && A[q + 1] != A[i]) {
q = pi[q];
}
if (A[q + 1] == A[i]) {
++q;
}
pi[i] = q;
}
q = 0;
int n = 0;
for (int i = 1; i <= N; ++i) {
while (q && A[q + 1] != B[i]) {
q = pi[q];
}
if (A[q + 1] == B[i]) {
++q;
}
if (q == M) {
q = pi[M];
++n;
if (n <= 1000) {
pos[n] = i - M;
}
}
}
fout << n << '\n';
for (int i = 1; i <= min(1000, n); ++i) {
fout << pos[i] << ' ';
}
fout << '\n';
return 0;
}