Pagini recente » Cod sursa (job #754400) | Cod sursa (job #1241265) | Cod sursa (job #355820) | Cod sursa (job #3312844) | Cod sursa (job #895450)
Cod sursa(job #895450)
#include<cstdio>
#include<cstring>
#include<vector>
#define INF 2000002
using namespace std;
char text[INF],s[INF];
int p[INF],k,lt,ls,max;
vector<int> ind;
void pref()
{
p[0]=-1;
int k=-1;
for(int i=1;i<ls;++i)
{
while(k>-1&&s[i]!=s[k+1])k=p[k];
if(s[i]==s[k+1])++k;
p[i]=k;
}
}
void kmp()
{
int k=-1;
for(int i=0;i<lt;++i)
{
while(k>-1&&text[i]!=s[k+1])k=p[k];
if(text[i]==s[k+1])++k;
if(k==ls-1){ind.push_back(i-k);k=p[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s);
gets(text);
ls=strlen(s);
lt=strlen(text);
pref();
kmp();
printf("%d\n",ind.size());
for(int i=0;i<ind.size()&&i<1000;++i)printf("%d ",ind[i]);
return 0;
}