Pagini recente » Cod sursa (job #1011578) | Cod sursa (job #365709)
Cod sursa(job #365709)
#include<iostream>
#include<string>
using namespace std;
#define LM 2000005
#define FOR(i,a,b)for(i=(a);i<=(b);++i)
int sl,tl,pi[LM],dim,pozitii[1005];
char S[LM],T[LM];
void get_pi()
{
int how_many=0,i;
pi[0]=0;
FOR(i,1,sl-1)
{
while(how_many && S[how_many]!=S[i]) how_many=pi[how_many];
if(S[how_many]==S[i]) ++how_many;
pi[i]=how_many;
}
}
inline void new_occurence(int pos)
{
//printf("%d\n",pos);
++dim;
if(dim<=1000) pozitii[dim]=pos;
}
void get_kmp()
{
int how_many=0,where=0;
while(where<tl)
{
while(how_many && S[how_many]!=T[where]) how_many=pi[how_many];
if(S[how_many]==T[where]) ++how_many;
if(how_many==sl)
{
new_occurence(where-sl+1);
how_many=pi[how_many];
}
++where;
}
}
int main()
{
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&S);
scanf("%s",&T);
sl=strlen(S);
tl=strlen(T);
get_pi();
get_kmp();
printf("%d\n",dim);
FOR(i,1,dim)
printf("%d ",pozitii[i]);
return 0;
}