Pagini recente » Cod sursa (job #162216) | Cod sursa (job #1785076) | Cod sursa (job #2777155) | Cod sursa (job #2764667) | Cod sursa (job #1004793)
#include <fstream>
#include <iostream>
using namespace std;
#define LE 4000666
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define sh short int
#include <cstring>
string s1,s2;
sh n,a[LE];
sh i,j,prfx[LE];
int main()
{
//f>>n;
//for(i=1;i<=n;++i) f>>b[i];
//for(i=2;i<=n;++i) a[i-1]=b[i]-b[i-1];
int st=0,dr=0;
//--n;
//for(i=1;i<=n;++i) cout<<a[i]<<" ";
//cout<<'\n';
f>>s1>>s2;
int n1=s1.length();
s1+=s2;
n=s1.length();
int result=0;
for(i=0;i<n;++i) a[i+1]=s1[i];
// cout<<s1<<'\n';
//for(i=1;i<=n;++i) cout<<a[i]-'A'<<" ";
//cout<<'\n';
for(i=2;i<=n;++i)
{
if (dr>=i)
{
int pos=i-st+1;
if (prfx[pos]+i<=dr)
{
prfx[i]=prfx[pos];
if (i>=n1+1&&prfx[i]>=n1) ++result;
continue;
}
}
if (dr<i) dr=i;
for(j=dr;j<=n&&a[j]==a[j-i+1];++j);
st=i;
dr=j-1;
prfx[i]=dr-st+1;
// cout<<prfx[i]<<" "<<dr<<'\n';
if (i>=n1+1&&prfx[i]>=n1) ++result;
}
// for(i=1;i<=n;++i) cout<<prfx[i]<<" ";
g<<result<<'\n';
int nr=0;
for(i=n1+1;i<=n;++i)
if (prfx[i]>=n1&&nr<1000)
{
g<<i-n1-1<<" ";
++nr;
}
// cout<<'\n'<<nr;
f.close();
g.close();
return 0;
}