Pagini recente » Cod sursa (job #757068) | Cod sursa (job #2233767) | Cod sursa (job #1140968) | simulare_de_oni_10 | Cod sursa (job #157582)
Cod sursa(job #157582)
#include<cstdio>
#include<cstring>
using namespace std;
const int size=2000001;
char a[size],b[size];
int n,m,i,j,k,pi[size],s[1001];
inline void kmp()
{
n=strlen(a);
k=0;
pi[1]=0;
for(i=2;i<=n;++i){
while(k>0 && a[k]!=a[i-1])
k=pi[k];
if(a[k]==a[i-1])
k++;
pi[i]=k;}
m=strlen(b);
k=0;
for(i=1;i<=m;++i){
while(k>0 && a[k]!=b[i-1])
k=pi[k];
if(a[k]==b[i-1]) k++;
if(k==n) {
s[0]++;
if(s[0]<=1000) s[s[0]]=i-n;}}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a,b);
kmp();
printf("%d\n",s[0]);
for(i=1;i<=1000&&i<=s[0];i++)
printf("%d ",s[i]);
fclose(stdout);
return 0;
}