Pagini recente » Cod sursa (job #1035576) | Cod sursa (job #575919) | Cod sursa (job #1815715) | Cod sursa (job #7493) | Cod sursa (job #559525)
Cod sursa(job #559525)
#include<fstream>
#include<iostream>
using namespace std;
int v[2000010],sol[2000010];
char a[2000010],b[2000010];
int la,lb,k=0;
void citire()
{
int i;
ifstream in("strmatch.in");
in.getline(a+1,1000,'\n');
in.getline(b+1,1000,'\n');
la=strlen(a);
lb=strlen(b);
/*for (i=la;i>0;i--)
a[i]=a[i-1];*/
a[0]=' ';
/*for (i=lb;i;i--)
b[i]=b[i-1];*/
b[0]=' ';
}
void prefix()
{
int i,q=0;
for (i=2,v[i]=0;i<=la;i++)
{
while (q&&a[q+1]!=a[i])
q=v[q];
if (a[q+1]==a[i])
++q;
v[i]=q;
}
}
void kmp()
{
int i,q=0;
for (i=1;i<=lb;i++)
{
while (q&&a[q+1]!=b[i])
q=v[q];
if (a[q+1]==b[i])
q++;
if (q==la)
{
k++;
if (k<=1000)
sol[k]=i-la;
}
}
}
int main()
{
int i,j;
citire();
prefix();
kmp();
ofstream out("strmatch.out");
out<<k<<'\n';
k=min(k,1000);
for (i=1;i<=k;i++)
out<<sol[i]<<" ";
out<<'\n';
/*for (i=1;i<=la+1;i++)
cout<<v[i]<<" ";*/
}