Pagini recente » Monitorul de evaluare | Cod sursa (job #2014731) | Cod sursa (job #264920) | Monitorul de evaluare | Cod sursa (job #1772040)
#include <iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
int p[2000100],d[2000100],k,i,m,n,nr;
char a[2000100],b[2000100];
int main()
{
ifstream f("strmatch.in");
f>>(a+1)>>(b+1);
f.close();
n=strlen(a+1);m=strlen(b+1);
k=0;p[1]=0;
for(i=2;i<=n;++i)
{
while(k>0&&a[k+1]!=a[i])k=p[k];
if(a[k+1]==a[i])++k;
p[i]=k;
}
k=0;nr=0;
for(i=1;i<=m;++i)
{
while(k>0&&a[k+1]!=b[i])k=p[k];
if(a[k+1]==b[i])++k;
d[i]=k;
if(k==n)++nr;
}
ofstream g("strmatch.out");g<<nr<<'\n';
for(i=1;i<=m;++i)
if(d[i]==n)
{
nr=i-n;g<<nr<<" ";
}
return 0;
}