Pagini recente » Cod sursa (job #508800) | Cod sursa (job #2307953) | Cod sursa (job #2030274) | Cod sursa (job #2102436) | Cod sursa (job #2175680)
#include <bits/stdc++.h>
#define NMAX 2000010
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;
}