Pagini recente » Cod sursa (job #710075) | Clasament FMI No Stress | Cod sursa (job #1345760) | Cod sursa (job #1044434) | Cod sursa (job #1356107)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005], B[2000005];
int N, M, pi[2000005], sol[2000005], dim, K;
void buildpi()
{
for (int i=2; i<=N; ++i)
{
while (K!=0 && A[K+1]!=A[i]) K=pi[K];
if (A[K+1]==A[i]) ++K;
pi[i]=K;
}
}
int main()
{
f>>(A+1)>>(B+1);
N=strlen(A+1); M=strlen(B+1);
buildpi(); K=0;
for (int i=1; i<=M; ++i)
{
while (K!=0 && A[K+1]!=B[i]) K=pi[K];
if (A[K+1]==B[i]) ++K;
if (K==N)
sol[++dim]=i-N, K=pi[N];
}
g<<dim<<'\n';
for (int i=1; i<=min(dim, 1000); ++i)
g<<sol[i]<<' ';
return 0;
}