Pagini recente » Cod sursa (job #2530492) | Cod sursa (job #2870284) | Cod sursa (job #2622787) | Cod sursa (job #2494318) | Cod sursa (job #428312)
Cod sursa(job #428312)
# include <fstream>
# include <iostream>
# include <cstring>
# define DIM 2000002
# define NMAX 1000
using namespace std;
char a[DIM], b[DIM];
int n, m, N, urm[DIM], p[NMAX+6];
void read ()
{
ifstream fin ("strmatch.in");
fin.getline(a, DIM);
fin.getline(b, DIM);
m=strlen(a);
n=strlen(b);
}
void urmatorul ()
{
int k=-1;
urm[0]=0;
for(int i=1;i<m;i++)
{
while (k>0 && a[k+1]!=a[i])k=urm[k];
if (a[k+1]==a[i])++k;
urm[i]=k;
}
}
void potrivire ()
{
int x=-1;
for (int i=0;i<n && N<NMAX;++i)
{
while (x>0 && a[x+1]!=b[i])x=urm[x];
if (a[x+1]==b[i])++x;
if (x==m-1)
{
p[++N]=i-m+1;
x=urm[x];
}
}
}
void afisare ()
{
ofstream fout ("strmatch.out");
fout<<N<<endl;
for (int i=1;i<=N;i++)
fout<<p[i]<<" ";
}
int main ()
{
read ();
urmatorul();
potrivire ();
afisare();
return 0;
}