Pagini recente » Cod sursa (job #1124532) | Cod sursa (job #1834483) | Cod sursa (job #2584563) | Cod sursa (job #808609) | Cod sursa (job #3329010)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,lps[2000001],nr,k,v[1001];
char a[2000001],b[2000001];
void calc()
{
k=0;
for(int i=1;i<=n-1;++i)
{
while(k && a[k]!=a[i-1]) k=lps[k];
if(a[k]==a[i-1]) k++;
lps[i]=k;
}
}
void gasire()
{
k=0;
for(int i=0;i<=m-1;++i)
{
while(k && a[k]!=b[i]) k=lps[k];
if(a[k]==b[i]) k++;
if(k==n)
{nr++;
if(nr<1000) v[nr]=i-n+1;
}
}
}
void afisare()
{g<<nr<<'\n';
for(int i=1;i<=min(nr,1000);++i)
g<<v[i]<<" ";
}
int main()
{
f.getline(a,2000001);
f.getline(b,2000001);
n=strlen(a);
m=strlen(b);
calc();
gasire();
afisare();
return 0;
}