Pagini recente » Cod sursa (job #2417423) | Cod sursa (job #3156466) | Cod sursa (job #594668) | Cod sursa (job #1809133) | Cod sursa (job #3031052)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int pi[2000005],nr,v[1005];
char a[2000005],b[2000005];
int main()
{
in>>a>>b;
int n=strlen(a),k=0;
pi[0]=0;
for(int i=1; i<n; ++i)
{
while(k>-1 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
++k;
pi[i]=k;
}
int m=strlen(b),q=-1;
for(int i=0; i<m; ++i)
{
while(q>-1 && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==n-1)
{
q=pi[n-1];
++nr;
if(nr<=1000)
v[nr]=i-n+1;
}
}
out<<nr<<"\n";
int lo=min(nr,1000);
for(int i=1; i<=lo; ++i)
out<<v[i]<<" ";
}
/*
n=5
abacd
p[1]=0;
for(i=2;i<=n;++i)
{
while(k>0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i]
++k;
pi[i]=k;
}
*/