Pagini recente » Diferente pentru preoni-2007/runda-finala/solutii intre reviziile 24 si 28 | Cod sursa (job #2450812) | Atasamentele paginii Clasament ce-o-sa-ma-injure-colegii | Cod sursa (job #2421140) | Cod sursa (job #2351840)
#include <bits/stdc++.h>
#define NMAX 2000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void citire();
int lg1,lg2;
char a[NMAX],b[NMAX];
int d[NMAX],r[NMAX],cate;
vector <int> v;
int main()
{citire();
return 0;
}
void citire()
{int i,k=0,gasit;
fin>>a+1>>b+1;
lg1=strlen(a+1);
lg2=strlen(b+1);
for(i=2;i<=lg1;i++)
if(a[k+1]==a[i])
{k++;d[i]=k;}
else
{
while(a[k+1]!=a[i] && k!=0)
{
k=d[k];
}
if(a[k+1]==a[i])
d[i]=k++;
else
d[i]=0;
}
// for(i=1;i<=lg1;i++)
// fout<<d[i]<<" ";
k=0;
for(i=1;i<=lg2;i++)
{if(b[i]==a[k+1])
{
k++;r[i]=k;
}
else
{while(a[k+1]!=b[i] && k!=0)
{
k=d[k];
}
if(a[k+1]==b[i])
r[i]=k++;
else r[i]=0;
}
if(r[i]==lg1)
{cate++;
if(cate<=1000)
v.push_back(i-lg1+1);
}
}
fout<<cate<<'\n';
for(i=0;i<v.size() ;i++)
fout<<v[i]-1<<" ";
}