Pagini recente » Cod sursa (job #142994) | Cod sursa (job #1803802) | Cod sursa (job #984816) | Cod sursa (job #2308483) | Cod sursa (job #2420137)
#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],K;
int ans;
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];
K=0;
Pi[1]=0;
for(int i=2;i<=lgA;i++)
{
while(K>0&&A[i]!=A[K+1]) 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++;
}
g<<ans<<'\n';
if(ans<=1000)
{
for(int i=1;i<=lgB;i++)
if(Di[i]==lgA) g<<i-lgA<<" ";
}
else
{
int cnt=0;
for(int i=1;i<=lgB&&cnt<=1000;i++)
if(Di[i]==lgA)
{
g<<i-lgA<<" ";
cnt++;
}
}
return 0;
}