Pagini recente » Cod sursa (job #163301) | Cod sursa (job #1077869) | Cod sursa (job #221274) | Cod sursa (job #431026) | Cod sursa (job #1379818)
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 2000005;
string A, B;
int pi[MAXN], pos[1025];
void make_prefix(void) {
int q = 0;
pi[1] = 0;
for(int i = 2; i < A.size(); ++i) {
while(q && A[q + 1] != A[i])
q = pi[q];
if(A[q + 1] == A[i])
++q;
pi[i] = q;
}
}
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
int q = 0, n = 0;
A.insert(A.begin(), ' ');
B.insert(B.begin(), ' ');
make_prefix();
for(int i = 1; i < B.size(); ++i) {
while(q && A[q + 1] != B[i])
q = pi[q];
if(A[q + 1] == B[i])
++q;
if (q == A.size() - 1) {
q = pi[A.size() - 1];
++n;
if(n <= 1000)
pos[n] = i - A.size() + 1;
}
}
cout << n << '\n';
for(int i = 1; i <= min(n, 1000); ++i)
cout << pos[i] << ' ';
return 0;
}