Pagini recente » Cod sursa (job #2259383) | Cod sursa (job #2160456) | Cod sursa (job #2420418) | Cod sursa (job #88503) | Cod sursa (job #1193011)
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char n[nmax],m[nmax];
int ln,lm,k,i,q,cont;
int pr[nmax],potr[nmax];
int main()
{
in>> (n + 1);
in>> (m + 1);
ln=strlen(n+1);
lm=strlen(m+1);
k=0;
cont=0;
pr[1]=0;
for(i=2;i<=ln;i++)
{
while(k&&n[k+1]!=n[i])
k=pr[k];
if(n[k+1]==n[i])
k++;
pr[i]=k;
}
q=0;
for(i=1;i<=lm;i++)
{
while(q&&n[q+1]!=m[i])
q=pr[q];
if(n[q+1]==m[i])
q++;
if(q==ln)
{
potr[++cont]=i-ln;
q = pr[q];
}
}
if (cont> 1000) cont = 1000;
out<<cont<<'\n';
for(i=1;i<=cont;i++)
out<<potr[i]<<" ";
out<<'\n';
return 0;
}