Pagini recente » Cod sursa (job #445488) | Cod sursa (job #442303) | Cod sursa (job #2853622) | Cod sursa (job #1362728) | Cod sursa (job #432250)
Cod sursa(job #432250)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char a[2000010],b[2000010];
int n,m,cnt,pia[2000010];
vector <int> poz;
void citire()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a);
m=strlen(b);
for (int i=n;i;--i)
a[i]=a[i-1];
a[0]='$';
for (int i=m;i;--i)
b[i]=b[i-1];
b[0]='$';
}
int main()
{
citire();
int i;
for (i=2;a[i];++i)
{
int y=pia[i-1];
while (a[y+1]!=a[i]&&y)
y=pia[y];
if (a[y+1]==a[i])
pia[i]=y+1;
}
int aux=0;
for (int i=1;b[i];++i)
{
int y=aux;
while (a[y+1]!=b[i]&&y)
y=pia[y];
if (a[y+1]==b[i])
aux=y+1;
else
aux=0;
if (aux==n)
{
++cnt;
if (poz.size()<1000)
poz.push_back(i-n);
}
}
printf("%d\n",cnt);
for (int i=0;i<poz.size();++i)
printf("%d ",poz[i]);
printf("\n");
return 0;
}