Pagini recente » Cod sursa (job #1129396) | Cod sursa (job #961573) | Cod sursa (job #2318081) | Cod sursa (job #2584417) | Cod sursa (job #3196674)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=2e6;
char a[2*N+2],b[N+1];
int pi[2*N+2];
int v[1001];
int main()
{
int aL,sL,cnt=0,i;
fin>>a;
fin>>b;
aL=strlen(a);
a[aL]='$';
strcat(a,b);
sL=strlen(a);
pi[0]=-1;
for(i=1;i<sL;i++)
{
pi[i]=pi[i-1];
while(pi[i]!=-1 && a[pi[i]+1]!=a[i])
pi[i]=pi[pi[i]];
if(a[pi[i]+1]==a[i])
pi[i]++;
}
for(i=aL+1;i<sL;i++)
{
if(pi[i]==aL-1)
{
cnt++;
if(cnt<=1000)
v[cnt]=i-2*aL;
}
}
fout<<cnt<<'\n';
for(i=1;i<=min(1000,cnt);i++)
fout<<v[i]<<" ";
return 0;
}