Pagini recente » Cod sursa (job #22810) | Cod sursa (job #1102688) | Cod sursa (job #998356) | Cod sursa (job #2591082) | Cod sursa (job #1537889)
#include <fstream>
#include <cstring>
#define nmax 2000010
using namespace std;
char a[nmax],b[nmax],pi[nmax];
int n,m,st[nmax],vf;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void precalc()
{
int i=0,j=1;
pi[i]=0;
while(j<n)
{
if(a[i]!=a[j])
{
if(i==0)
pi[j++]=0;
else
i=pi[i-1];
}
else
{
pi[j]=i+1;
i++;
j++;
}
}
}
void rezolv()
{
int i=0,j=0;
while(j<m)
{
if(a[i]!=b[j])
{
if(i==0)
j++;
else
i=pi[i-1];
}
else
{
i++;
j++;
if(i==n)
st[++vf]=j-n;
}
}
}
void afisare()
{
fout<<vf<<"\n";
for(int i=1;i<=vf;i++)
fout<<st[i]<<" ";
fout<<"\n";
}
int main()
{
fin>>a>>b;
n=strlen(a);
m=strlen(b);
precalc();
rezolv();
afisare();
return 0;
}