Pagini recente » Cod sursa (job #1530109) | Cod sursa (job #1518568) | Cod sursa (job #1654484) | Cod sursa (job #2423876) | Cod sursa (job #383602)
Cod sursa(job #383602)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define M 2000000
using namespace std;
int n,m,nr,urm[M],v[1001];
char s[M],p[M],aux[M];
void prefix()
{
int q,k;
q=2;
urm[1]=0;
k=0;
for(q=2;q<=m;q++)
{
while(k>0&&p[k+1]!=p[q])
k=urm[k];
if(p[k+1]==p[q])
k++;
urm[q]=k;
}
}
void solve()
{
int i,q;
q=m+1;
for(i=1;i<=n;i++)
{
while(q>0&&p[q+1]!=s[i])
q=urm[q];
if(s[i]==p[q+1])
q++;
if(q==m)
{
nr++;
if(nr<=1000)
v[nr]=i-m;
else
break;
}
}
}
void print()
{
int i ;
printf("%d\n" , nr);
for(i=1;i<nr;i++)
printf("%d " , v[i]);
printf("%d\n" , v[nr]);
}
int main ()
{
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
scanf("%s" , &aux);
p[0]=' ';
strcat(p,aux);
m=strlen(p)-1;
s[0]=' ';
scanf("%s" , &aux);
strcat(s,aux);
n=strlen(s)-1;
prefix();
solve();
print();
return 0;
}