Pagini recente » Cod sursa (job #390124) | Cod sursa (job #1605793) | Cod sursa (job #1780023) | Cod sursa (job #892304) | Cod sursa (job #929600)
Cod sursa(job #929600)
#include<stdio.h>
#include<vector>
#define maxn 2000005
using namespace std;
int m,n,nr;
char p[maxn],t[maxn];
int urm[maxn];
vector <int> sol;
void cit()
{
char c;
scanf("%c",&c);
while(c!='\n')
{
p[++m]=c;
scanf("%c",&c);
}
scanf("%c",&c);
while(c!='\n')
{
t[++n]=c;
scanf("%c",&c);
}
}
void pref()
{
int i,k=0;
urm[1]=0;
for(i=2;i<=m;i++)
{
while(k>0 && p[k+1]!=p[i]) k=urm[k];
if(p[k+1]==p[i]) k++;
urm[i]=k;
}
}
void solve()
{
int i,k=0;
for(i=1;i<=n;i++)
{
while(k>0 && p[k+1]!=t[i]) k=urm[k];
if(p[k+1]==t[i]) k++;
if(k==m)
{
nr++;
if(nr<=1000) sol.push_back(i-m);
k=urm[k];
}
}
}
void afis()
{
printf("%d\n",sol.size());
for(unsigned int i=0;i<sol.size();i++)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cit();
pref();
solve();
afis();
fclose(stdin);
fclose(stdout);
return 0;
}