Pagini recente » Cod sursa (job #1166555) | Cod sursa (job #1847512) | Cod sursa (job #2274314) | Cod sursa (job #2246128) | Cod sursa (job #1965165)
/**
Z-Algorithm
*/
#include<bits/stdc++.h>
#define maxN 4000005
using namespace std;
char s[maxN],s1[maxN];
int n,m,st,dr,z[maxN],j;
vector<int> sol;
vector<int>::iterator it;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
scanf("\n");
scanf("%s",s1+1);
m=strlen(s1+1);
strcat(s+1,s1+1);
// printf("%s\n",s+1);
st=0;
dr=0;
for(int i=2;i<=(n+m);i++)
{
if(dr<=i)
{
z[i]=0;
j=0;
while((i+j)<=(n+m) && s[i+j]==s[j+1])
{
j++;
z[i]++;
}
if(z[i])
{
st=i;
dr=i+z[i]-1;
}
}
else
{
z[i]=z[i-st+1];
if((i+z[i]-1)>=dr)
{
j=z[i];
while((i+j)<=(n+m) && s[j+1]==s[j+i]) j++,z[i]++;
// z[i]=j;
}
if((i+z[i]-1)>dr)
{
dr=i+z[i]-1;
st=i;
}
}
}
/* for(int i=1;i<=n+m;i++)
printf("%d ",z[i]);
printf("\n");*/
for(int i=n+1;i<=n+m;i++)
if(z[i]>=n)
{
sol.push_back(i);
}
while(sol.size()>1000) sol.pop_back();
printf("%d\n",sol.size());
sort(sol.begin(),sol.end());
for(vector<int>::iterator it=sol.begin();it!=sol.end();it++)
printf("%d ",*it-n-1);
return 0;
}