Pagini recente » Cod sursa (job #2503220) | Cod sursa (job #704099) | 343242354534 | Cod sursa (job #2138612) | Cod sursa (job #2421919)
#include <bits/stdc++.h>
#define Dim 2000009
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[Dim],B[Dim];
int lgA,lgB,Pi[Dim],Di[Dim],Poz[1005],ans,K;
int main()
{
f.get(A,Dim); f.get();
f.get(B,Dim);
lgA=strlen(A); lgB=strlen(B);
for(int i=lgA;i>=1;i--) A[i]=A[i-1];
for(int i=lgB;i>=1;i--) B[i]=B[i-1];
Pi[1]=0; K=Pi[1];
for(int i=2;i<=lgA;i++)
{
while(K>0&&A[K+1]!=A[i]) K=Pi[K];
if(A[i]==A[K+1]) K++;
Pi[i]=K;
}
K=0;
for(int i=1;i<=lgB;i++)
{
while(K>0&&B[i]!=A[K+1]) K=Pi[K];
if(B[i]==A[K+1]) K++;
Di[i]=K;
if(Di[i]==lgA)
{
ans++;
if(ans<=1000) Poz[ans]=i-lgA;
}
}
g<<ans<<'\n';
for(int i=1;i<=min(ans,1000);i++) g<<Poz[i]<<" ";
return 0;
}