Pagini recente » Cod sursa (job #1140792) | Cod sursa (job #1099805) | Cod sursa (job #1164965) | Cod sursa (job #3323165) | Cod sursa (job #2883896)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int const N=(int)1e6*2+7;
char txt[N],f[N];
int ps[N];
int n,m;
void prefix()
{
ps[0]=0;
int j=0;
for(int i=1;i<n;i++)
{
while(j && f[j]!=f[i])
j=ps[j-1];
if(f[j]==f[i])
{
j++;
ps[i]=j;
}
else
ps[i]=0;
///cout<<ps[i]<<' ';
}
}
int R[N];
void solve()
{
int j=0,r=0;
for(int i=0;i<m;i++)
{
if(j==n)
{
R[r++]=i-j;
j=ps[j-1];
}
while(j && f[j]!=txt[i])
j=ps[j-1];
if(txt[i]==f[j])
j++;
}
if(j==n)
R[r++]=m-j;
fout<<r<<'\n';
r=min(r,1000);
for(int i=0;i<r;i++)
fout<<R[i]<<' ';
}
int main()
{
fin>>f>>txt;
n=strlen(f);
m=strlen(txt);
prefix();
solve();
}