Pagini recente » Cod sursa (job #1636287) | Cod sursa (job #1345700) | Cod sursa (job #2808123) | Cod sursa (job #2228219) | Cod sursa (job #2063220)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000000],s[2000000];
int p[2000000],n,af,sol[2000000];
void Citire()
{
cin.getline(s,1000);
cin.getline(a,1000);
}
void KMP()
{
int i=0,j=0;
while (j<strlen(s))
{
while (a[i]==s[j])
{
i++;
j++;
if (i==n)
{
sol[af]=j-n;
af++;
if (af==1000)
return;
i=0;
j=j-n+1;
}
}
i=p[i-1];
if (a[i]!=s[j])
j++;
}
}
void Prefix()
{
int i=0;
for (int j=1; j<n; j++)
{
if (a[i]==a[j])
{
p[j]=1+p[j-1];
i++;
}
else
{
i=p[j-1];
if (a[j]==a[i])
{
p[j]=1;
i++;
}
}
}
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
Citire();
n=strlen(a);
Prefix();
KMP();
cout<<af<<endl;
for (int i=0;i<af;i++)
cout<<sol[i]<<" ";
/*for (int i=0; i<n; i++)
cout<<p[i]<<" ";*/
return 0;
}