Pagini recente » Cod sursa (job #1048016) | Cod sursa (job #723082) | Cod sursa (job #724467) | Cod sursa (job #758922) | Cod sursa (job #559516)
Cod sursa(job #559516)
#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,1000,'\n');
in.getline(b,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]<<" ";*/
}