Pagini recente » Cod sursa (job #3187822) | Cod sursa (job #3274113) | Cod sursa (job #2547491) | Cod sursa (job #1136505) | Cod sursa (job #540999)
Cod sursa(job #540999)
// Potrivirea sirurilor - KMP
#include <fstream>
#define LMAX 2000011
using namespace std;
char a[LMAX],b[LMAX];
int nr,poz[1001],pi[LMAX];
inline int minim(int a, int b)
{
if(a<=b)
return a;
return b;
}
void make_prefix()
{
int i,k,lg;
lg=strlen(a)-1;
pi[1]=0;
k=0;
for(i=2;i<=lg;i++)
{
while( k>0 && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
k=k+1;
pi[i]=k;
}
}
int main()
{
int i,lga,lgb,q;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
lga=strlen(a);
lgb=strlen(b);
for(i=lga;i>0;i--) a[i]=a[i-1]; a[0]=' ';
for(i=lgb;i>0;i--) b[i]=b[i-1]; b[0]=' ';
make_prefix();
q=0;
for(i=1;i<=lgb;i++)
{
while(q && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
q=q+1;
if(q==lga)
{
q=pi[lga];
nr++;
if(nr<=1000)
poz[nr]=i-lga;
}
}
g<<nr<<"\n";
for(i=1;i<=minim(nr,1000);i++)
g<<poz[i]<<" ";
g<<"\n";
return 0;
}