Pagini recente » Cod sursa (job #2086987) | Cod sursa (job #2348966) | Cod sursa (job #2018970) | Istoria paginii jc2016/runda-2 | Cod sursa (job #2300380)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char c[2000010],a[2000010];
int i,k,n,m,nr,p[2000010],sol[2000010];
int main()
{
f>>c+1;
f>>a+1;
n=strlen(c+1);
m=strlen(a+1);
for(i=2; i<=n; i++)
{
for(; k!=0 && c[k+1]!=c[i];) k=p[k];
if(c[k+1] == c[i])k++;
p[i]=k;
}
k=0;
for(i=1; i<=m; i++)
{
for(; k!=0 && c[k+1]!=a[i];)k=p[k];
if(c[k+1]==a[i])k++;
if(k==n)
{
nr++;
if(nr<=1000)sol[nr]=i-n;
}
}
g<<nr<<'\n';
for(i=1; i<=min(nr,1000); i++)
g<<sol[i]<<" ";
return 0;
}