Pagini recente » Cod sursa (job #447724) | Cod sursa (job #2073859) | Cod sursa (job #2740006) | Cod sursa (job #444713) | Cod sursa (job #758305)
Cod sursa(job #758305)
#include<fstream>
#include<string>
const int MAX=2000005;
using namespace std;
string a,b;
int m,n,nr,sol[1005],next[MAX];
void readdata(){
ifstream fin("strmatch.in");
int i; string aux;
getline(fin,a); m=a.length();
getline(fin,b); n=b.length();
aux=a[m-1]; a.append(aux);
aux=b[n-1]; b.append(aux);
for(i=m;i>0;--i)a[i]=a[i-1];
for(i=n;i>0;--i)b[i]=b[i-1];
fin.close();
}
void make_prefix()
{
int k=0,x;
next[1]=0;
for(x=2;x<=m;++x)
{
while(k && a[k+1]!=a[x])k=next[k];
if(a[k+1]==a[x])++k;
next[x]=k;
}
}
void solve()
{
int i,k=0;
make_prefix();
for(i=1;i<=n;++i)
{
while(k && a[k+1]!=b[i])k=next[k];
if(a[k+1]==b[i])++k;
if(k==m)
{
++nr;
if(nr<=1000)
sol[nr]=i-m;
k=next[k];
}
}
}
void writedata()
{
ofstream fout("strmatch.out");
fout<<nr<<'\n';
if(nr>1000)nr=1000;
for(int i=1;i<=nr;++i)
fout<<sol[i]<<' ';
fout.close();
}
int main(void){
readdata();
solve();
writedata();
return 0;
}