Pagini recente » Cod sursa (job #249016) | Cod sursa (job #2690439) | Cod sursa (job #663924) | Cod sursa (job #2590842) | Cod sursa (job #1376998)
#include <cstdio>
#include <vector>
#include <cstring>
#define Nmax 2000005
using namespace std;
char A[Nmax],B[Nmax];
int P[Nmax],N,M,nrsol = 0;
vector<int> sol;
void make_prefix()
{
int q = 0;
for(int i = 2; i <= N; ++i)
{
while(q && A[i] != A[q+1])
q = P[q];
if(A[i] == A[q+1])
++q;
P[i] = q;
}
}
void kmp()
{
int q = 0;
for(int i = 1; i <= M; ++i)
{
while(q && B[i] != A[q+1])
q = P[q];
if(B[i] == A[q+1])
++q;
if(q == N){
q = P[q];
++nrsol;
if(sol.size() < 1000)
sol.push_back(i-N);
}
}
}
void print()
{
printf("%d\n",nrsol);
for(int i = 0; i < sol.size(); ++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
A[0] = '#';
B[0] = '#';
N = strlen(A+1);
M = strlen(B+1);
make_prefix();
kmp();
print();
return 0;
}