Pagini recente » Cod sursa (job #1153597) | Cod sursa (job #1116997) | Cod sursa (job #1579560) | Istoria paginii runda/oji20082009/clasament | Cod sursa (job #1204394)
// z-algo
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
const int nmax = 2000005;
int n,m,i,l,r,k,z[nmax],p[nmax],sol,S[nmax];
char a[nmax],b[nmax];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",b+1);
scanf("%s",a+1);
n=strlen(a+1);
m=strlen(b+1);
// z[i] = lungimea celui mai lung prefix al lui b care incepe pe b[i]
l=r=z[1]=0;
for(i=2;i<=m;i++)
{
if(i>r)
{
l=i; r=i-1;
while(r<m && b[r+1]==b[r-l+2]) r++;
z[i]=r-l+1;
}
else
{
k=i-l+1;
if(i+z[k]<=r)
{
z[i]=z[k];
}
else
{
l=i;
while(r<m && b[r+1]==b[r-l+2]) r++;
z[i]=r-l+1;
}
}
}
// p[i] = lungimea celui mai lung prefix a lui b care incepe pe a[i]
l=r=0;
for(i=1;i<=n;i++)
{
if(i>r)
{
l=i; r=i-1;
while(r<n && a[r+1]==b[r-l+2]) r++;
p[i]=r-l+1;
}
else
{
k=i-l+1;
if(i+z[k]<=r)
{
p[i]=z[k];
}
else
{
l=i;
while(r<n && a[r+1]==b[r-l+2]) r++;
p[i]=r-l+1;
}
}
}
for(i=1;i<=n;i++)
{
if(p[i]==m)
{
sol++;
if(sol<=1000) S[sol]=i-1;
}
}
printf("%d\n",sol);
for(i=1;i<=min(sol,1000);i++) printf("%d ",S[i]);
return 0;
}