Pagini recente » Istoria paginii runda/tpsimulare/clasament | Cod sursa (job #2295263) | Cod sursa (job #2948031) | Cod sursa (job #2449080) | Cod sursa (job #2407921)
#include<bits/stdc++.h>
using namespace std;
const int maxN=(2e6)+1;
char a[2*maxN],p[maxN],s[maxN];
int z[2*maxN],st,dr,sz;
vector<int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",p+1);
scanf("\n");
scanf("%s",s+1);
strcpy(a+1,p+1);
strcat(a+1,s+1);
int n=strlen(p+1);
int m=strlen(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) && a[1+z[i]]==a[i+z[i]]) z[i]++;
if(i+z[i]-1>dr)
{
dr=i+z[i]-1;
st=i;
}
}
for(int i=n+1;i<=n+m;i++)
if(z[i]>=n)
{
sz++;
if(sz<=1000) sol.push_back(i-n-1);
}
printf("%d\n",sz);
for(auto it:sol)
printf("%d ",it);
printf("\n");
return 0;
}