Pagini recente » Cod sursa (job #1592770) | Cod sursa (job #932062) | Cod sursa (job #1555221) | Cod sursa (job #436600) | Cod sursa (job #1579179)
#include <bits/stdc++.h>
using namespace std;
char A[2000005],B[2000005];
int P[2000005],N,M,cnt;
vector<int> poz;
void Prefix()
{
int q = 0;
for(int i = 2; i <= N; ++i)
{
while(q && A[i] != A[q + 1])
q = P[q];
q += A[i] == A[q + 1];
P[i] = q;
}
}
void Match_KMP()
{
int q = 0;
for(int i = 1; i <= M; ++i)
{
while(q && B[i] != A[q + 1])
q = P[q];
q += B[i] == A[q+1];
if(q == N)
{
++cnt;
q = P[q];
if(poz.size() < 1000)
poz.push_back(i-N);
}
}
}
void Read()
{
scanf("%s%s",A+1,B+1);
A[0] = B[0] = '#';
N = strlen(A+1);
M = strlen(B+1);
}
void Print()
{
printf("%d\n",cnt);
for(auto it : poz)
printf("%d ",it);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
Read();
Prefix();
Match_KMP();
Print();
return 0;
}