Pagini recente » Cod sursa (job #3287353) | Cod sursa (job #2972324) | Cod sursa (job #3212081) | Cod sursa (job #1218498) | Cod sursa (job #1168891)
#include <cstdio>
#include <cstring>
using namespace std;
char A[2000001],B[2000001];
int total,pi[2000001],m,n,sol[1005];
void Prefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= m; ++i)
{
while (q && A[q+1] != A[i])
q = pi[q];
if (A[q+1] == A[i])
++q;
pi[i] = q;
}
}
void Solve()
{
int q = 0;
for (int i = 1; i <= n; ++i)
{
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == m)
{
q = pi[m];
if(total < 1000)
sol[total] = i-m;
total++;
}
}
}
void Show()
{
printf("%d\n",total);
for(int i = 0; i < total; i++)
printf("%d ",sol[i]);
}
int main(){
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
m=strlen(A+1);
n=strlen(B+1);
Prefix();
Solve();
Show();
return 0;
}