Pagini recente » Cod sursa (job #1845741) | Cod sursa (job #2495012) | Cod sursa (job #127747) | Cod sursa (job #3263397) | Cod sursa (job #1623987)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
const int Nmax = 2000666;
string A, B;
int M[Nmax];
int ans[1024], N = 0;
void computeMatch() {
M[0] = -1;
for(int k = 0; k+1 < A.size(); ++k) {
int i = M[k];
while(i >= 0) {
if (A[k+1] == A[i+1]) {
M[k+1] = i+1;
break;
}
i = M[i];
}
if (i == -1) {
if (A[k+1] == A[0])
M[k+1] = 0;
else
M[k+1] = -1;
}
}
}
int main() {
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin >> A >> B;
computeMatch();
int i = -1;
for(int k = 0; k < B.size(); ++k) {
while(i >= 0) {
if (B[k] == A[i+1]) {
++i;
break;
}
i = M[i];
}
if (i == -1 && B[k] == A[0]) {
++i;
}
if (i == A.size() - 1) {
if (N < 1000)
ans[N] = k - i;
++N;
i = M[i];
}
}
fout << N << endl;
for (int i = 0; i < N && i < 1000; ++i) {
fout << ans[i] << ' ';
}
fout << endl;
return 0;
}