Pagini recente » Cod sursa (job #360137) | Rating Comanadariu Madalina Ioana (madalyna) | Cod sursa (job #185904) | Cod sursa (job #2671039) | Cod sursa (job #2173395)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[NMAX],B[NMAX];
int pi[NMAX],ans[1010],a,b,nr;
void prefix()
{
int q=0;
for(int i=2;i<=a;++i)
{
while(q&&A[q+1]!=A[i])
q=pi[q];
if(A[q+1]==A[i])
++q;
pi[i]=q;
}
}
int main()
{
f>>A+1; a=strlen(A+1);
f>>B+1; b=strlen(B+1);
prefix();
int q=0;
for(int i=1;i<=b;++i)
{
while(q&&A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==a)
{
q=pi[q];
++nr;
if(nr<=1000)
ans[nr]=i-a;
}
}
g<<nr<<"\n";
for (int i = 1; i <= min(nr, 1000); ++i)
g<<ans[i]<<" ";
return 0;
}