Pagini recente » Cod sursa (job #2098061) | Cod sursa (job #556833) | Cod sursa (job #955454) | Cod sursa (job #2642774) | Cod sursa (job #305237)
Cod sursa(job #305237)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define mini(a,b) ((a<b) ? a:b)
#define IMAX 2000001
ifstream f ("strmatch.in");
ofstream o ("strmatch.out");
int n,m,i,sir[IMAX],nrap,ap[1001];
char a[IMAX],b[IMAX];
void functie()
{
int k;
sir[0]=-1;
// sir[-1]=-1;
k=-1;
for(i=1;i<m;i++)
{
while( k>-1 && a[k+1]!=a[i] )
k=sir[k];
if(a[k+1]==a[i])
k++;
sir[i]=k;
}
}
void kmp()
{
int j;
n=strlen(b);
m=strlen(a);
functie();
j=-1;
for(i=0;i<n;i++)
{
while(j>-1 && a[j+1]!=b[i])
j=sir[j];
if(a[j+1]==b[i])
j++;
if(j==m-1)
{
// o<<"\n Modelul apare cu deplasamentul "<<i-m+1;
j=sir[j];
nrap++;
if(nrap<=1000)
ap[nrap]=i-m+1;
}
}
}
int main()
{
int i;
f.get(a,IMAX);
f.get();
f.get(b,IMAX);
kmp();
o<<nrap<<"\n";
for(i=1;i<=mini(nrap,1000);i++)
o<<ap[i]<<" ";
return 0;}