Pagini recente » Monitorul de evaluare | Cod sursa (job #1965155) | Cod sursa (job #1965866) | Cod sursa (job #1965152) | Cod sursa (job #1965823)
/**
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("%s",s1);
m=strlen(s1);
strcat(s+1,s1);
// printf("%s\n",s+1);
for(int i=2;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[1+z[i]]) z[i]++;
if(dr<i+z[i]-1)
{
dr=i+z[i]-1;
st=i;
}
}
for(int i=n+1;i<=n+m;i++)
if(z[i]==n) sol.push_back(i-n-1);
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;
}