Pagini recente » Cod sursa (job #268335) | Cod sursa (job #1145774) | Cod sursa (job #1680712) | Cod sursa (job #2500221) | Cod sursa (job #2675224)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[2000000], p[2000000];
int nr, poz[2000000], lps[2000000];
void citire()
{
scanf("%s\n", p);
scanf("%s\n", s);
}
void lps_make()
{
lps[0]=0;
int len=0;
for(int i=1;i<strlen(p);i++)
{
if(p[i]==p[len])
lps[i]=++len;
else
{
if(len)
len=lps[len-1], i--;
else
lps[i]=0;
}
}
}
void comparare()
{
int j=0;
for(int i=0;i<strlen(s);i++)
{
if(s[i]==p[j])
j++;
else
{
if(j)
j=lps[j-1], i--;
}
if(j==strlen(p))
poz[nr++]=i-j+1, j=lps[j-1];
}
}
void afisare()
{
cout<<nr<<'\n';
for(int i=0;i<nr;i++)
cout<<poz[i]<<' ';
}
int main()
{
freopen("strmatch.in","r", stdin);
freopen("strmatch.out","w", stdout);
citire();
lps_make();
comparare();
afisare();
return 0;
}