Pagini recente » Cod sursa (job #2243898) | Cod sursa (job #1830289) | Cod sursa (job #2172318) | Cod sursa (job #1823233) | Cod sursa (job #1965866)
/**
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);
scanf("\n");
n=strlen(s);
scanf("%s",s1);
m=strlen(s1);
strcat(s+1,s1);
// printf("%s\n",s+1);
st=-1;
dr=-1;
for(int i=1;i<(n+m);i++)
{
if(dr>=i) z[i]=min(z[i-st+1],dr-i+1);
while((i+z[i])<(n+m) && s[i+z[i]]==s[z[i]]) z[i]++;
if(dr<i+z[i]-1)
{
dr=i+z[i]-1;
st=i;
}
}
for(int i=n;i<=n+m;i++)
if(z[i]==n) sol.push_back(i-n);
printf("%d\n",sol.size());
sort(sol.begin(),sol.end());
int sz=sol.size();
int x=min(1000,sz);
for(int i=0;i<x;i++)
printf("%d ",sol[i]);
return 0;
}