Pagini recente » Cod sursa (job #954571) | Cod sursa (job #3241186) | Cod sursa (job #1280057) | Cod sursa (job #812816) | Cod sursa (job #1790696)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000005;
vector<int> sol;
char A[Nmax],B[Nmax];
int P[Nmax], N, M, total;
void make_prefix()
{
int q = 0;
for(int i = 2; i <= N; ++i) {
while(q && A[q + 1] != A[i])
q = P[q];
q += A[q+1] == A[i];
P[i] = q;
}
}
void make_match()
{
int q = 0;
for(int i = 1; i <= M; ++i) {
while(q && A[q + 1] != B[i])
q = P[q];
q += A[q+1] == B[i];
if(q == N) {
q = P[q];
++total;
if(total <= 1000) {
sol.push_back(i - N);
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", A + 1); A[0] = '#'; N = strlen(A + 1);
scanf("%s", B + 1); B[0] = '#'; M = strlen(B + 1);
make_prefix();
make_match();
cout << total << "\n";
for(auto it : sol)
cout << it << " ";
return 0;
}