Pagini recente » Cod sursa (job #200324) | Cod sursa (job #11874) | Cod sursa (job #2494889) | Cod sursa (job #2414929) | Cod sursa (job #2071639)
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char s[2000000],p[1000000];
int n,m,pi[2000000],sol[2000000],nr;
void construct ()
{
int k; pi[0]=-1;
for(int i=1;i<=m;i++)
{
k=pi[i-1];
while(k>-1 && p[i]!=p[k+1]) k=pi[k];
if(p[i]==p[k+1]) ++k;
pi[i]=k;
}
}
void solve ()
{
int k;
for(int i=0;i<=n;i++)
{
if(i>0) k=sol[i-1]; else k=-1;
while(k>-1 && s[i]!=p[k+1]) k=pi[k];
if(s[i]==p[k+1]) k++;
sol[i]=k;
if(k==m) nr++;
}
}
void read ()
{
cin>>p>>s;
n=strlen(s)-1;
m=strlen(p)-1;
}
void write ()
{ int y=0;
cout<<nr<<"\n";
for(int i=0;i<=n;i++)
{
if(sol[i]==m) cout<<i-m<<" ",y++;
if(y==1000) break;
}
}
int main()
{
read();
construct();
solve();
write();
cin.close();
cout.close();
return 0;
}